Vaughan Pratt

Last updated

Vaughan Pratt
VaughanPratt.JPG
Born
Vaughan Ronald Pratt

(1944-04-12) April 12, 1944 (age 79)
Melbourne, Australia
Education Stanford University (1972)
University of Sydney (1970)
Known for Knuth–Morris–Pratt algorithm
Pratt certificate
Pratt parser
Scientific career
Fields Computer science
Institutions Stanford University
MIT
Academic advisors Donald Knuth
Website boole.stanford.edu/pratt.html

Vaughan Pratt (born April 12, 1944) is a Professor Emeritus at Stanford University, who was an early pioneer in the field of computer science. Since 1969, Pratt has made several contributions to foundational areas such as search algorithms, sorting algorithms, and primality testing. More recently, his research has focused on formal modeling of concurrent systems and Chu spaces.

Contents

Career

Raised in Australia and educated at Knox Grammar School, where he was dux in 1961, Pratt attended Sydney University, where he completed his masters thesis in 1970, related to what is now known as natural language processing. He then went to the United States, where he completed a Ph.D. thesis at Stanford University in only 20 months under the supervision of advisor Donald Knuth. His thesis focused on analysis of the Shellsort sorting algorithm and sorting networks. [1]

Pratt was an assistant professor at MIT (1972 to 1976) and then associate professor (1976 to 1982). In 1974, working in collaboration with Knuth and James H. Morris, Pratt completed and formalized work he had begun in 1970 as a graduate student at Berkeley; the coauthored result was the Knuth–Morris–Pratt pattern matching algorithm. In 1976, he developed the system of dynamic logic, a modal logic of structured behavior.

He went on sabbatical from MIT to Stanford (1980 to 1981), and was appointed a full professor at Stanford in 1981.

Pratt directed the SUN workstation project at Stanford from 1980 to 1982. He contributed in various ways to the founding and early operation of Sun Microsystems, acting in the role of consultant for its first year, then, taking a leave of absence from Stanford for the next two years, becoming director of research, and finally resuming his role as a consultant to Sun and returning to Stanford in 1985.

He also designed the Sun Microsystems logo, [2] which features four interleaved copies of the word "sun"; it is an ambigram.

Pratt became professor emeritus at Stanford in 2000.

Major contributions

A number of well-known algorithms bear Pratt's name. Pratt certificates, short proofs of the primality of a number, demonstrated in a practical way that primality can be efficiently verified, placing the primality testing problem in the complexity class NP and providing the first strong evidence that the problem is not co-NP-complete. [3] The Knuth–Morris–Pratt algorithm, which Pratt designed in the early 1970s together with fellow Stanford professor Donald Knuth and independently from Morris, is still the most efficient general string searching algorithm known today. [4] Along with Blum, Floyd, Rivest, and Tarjan, he described median of medians, the first worst-case optimal selection algorithm. [5]

Useful tool building

Pratt built some useful tools. In 1976, he wrote an MIT AI Lab working paper about CGOL, an alternative syntax for MACLISP that he had designed and implemented based on his paradigm for top-down operator precedence parsing. [6] His parser is sometimes called a "Pratt parser" [7] and has been used in later systems, such as MACSYMA. Douglas Crockford also used it as the underlying parser for JSLint. [8] Pratt also implemented a TECO-based text editor named "DOC", which was later renamed to "ZED". [9]

In 1999, Pratt built the world's smallest (at the time) web server—it was the size of a matchbox. [10] [11]

Other contributions

Pratt was credited in a 1995 Byte magazine article for proposing that the Pentium FDIV bug might have worse consequences than either Intel or IBM was predicting at the time. [12] [13]

Today Pratt has a wide influence. In addition to his Stanford professorship, he holds membership in at least seven professional organizations. He is a fellow of the Association for Computing Machinery and is on the editorial board of three major mathematics journals. He was also the founder, chairman, and CTO of TIQIT Computers, Inc. for the ten years prior to when it closed its doors in 2010.

Related Research Articles

<span class="mw-page-title-main">Donald Knuth</span> American computer scientist and mathematician (born 1938)

Donald Ervin Knuth is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer science. Knuth has been called the "father of the analysis of algorithms".

<span class="mw-page-title-main">Sorting algorithm</span> Algorithm that arranges lists in order

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

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

Robert Endre Tarjan is an American computer scientist and mathematician. He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.

<span class="mw-page-title-main">Ron Rivest</span> American cryptographer

Ronald Linn Rivest is a cryptographer and computer scientist whose work has spanned the fields of algorithms and combinatorics, cryptography, machine learning, and election integrity. He is an Institute Professor at the Massachusetts Institute of Technology (MIT), and a member of MIT's Department of Electrical Engineering and Computer Science and its Computer Science and Artificial Intelligence Laboratory.

<span class="mw-page-title-main">Robert Sedgewick (computer scientist)</span> American computer scientist

Robert Sedgewick is an American computer scientist. He is the founding chair and the William O. Baker Professor in Computer Science at Princeton University and was a member of the board of directors of Adobe Systems (1990–2016). He previously served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Institute for Defense Analyses, and INRIA. His research expertise is in algorithm science, data structures, and analytic combinatorics. He is also active in developing the college curriculum in computer science and in harnessing technology to make that curriculum available to anyone seeking the opportunity to learn from it.

<span class="mw-page-title-main">Robert W. Floyd</span> American computer scientist (1936–2001)

Robert W Floyd was a computer scientist. His contributions include the design of the Floyd–Warshall algorithm, which efficiently finds all shortest paths in a graph and his work on parsing; Floyd's cycle-finding algorithm for detecting cycles in a sequence was attributed to him as well. In one isolated paper he introduced the important concept of error diffusion for rendering images, also called Floyd–Steinberg dithering. He pioneered in the field of program verification using logical assertions with the 1967 paper Assigning Meanings to Programs. This was a contribution to what later became Hoare logic. Floyd received the Turing Award in 1978.

<span class="mw-page-title-main">Manuel Blum</span> Venezuelan computer scientist

Manuel Blum is a Venezuelan born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".

The following timeline of algorithms outlines the development of algorithms since their inception.

In computer science, a selection algorithm is an algorithm for finding the th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes time .

Kenneth Edward Batcher was an American academic who was emeritus professor of Computer Science at Kent State University. He also worked as a computer architect at Goodyear Aerospace in Akron, Ohio for 28 years.

In computer science, an operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator precedence parsers to convert from the human-readable infix notation relying on order of operations to a format that is optimized for evaluation such as Reverse Polish notation (RPN).

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled Algorithms Unlocked. He is an emeritus professor of computer science at Dartmouth College and former Chairman of the Dartmouth College Department of Computer Science. Between 2004 and 2008 he directed the Dartmouth College Writing Program. His research interests are algorithm engineering, parallel computing, and speeding up computations with high latency. In 2022, he was elected as a Democratic member of the New Hampshire House of Representatives.

James Hiram Morris is a professor (emeritus) of Computer Science at Carnegie Mellon. He was previously dean of the Carnegie Mellon School of Computer Science and Dean of Carnegie Mellon Silicon Valley.

CGOL is an alternative syntax featuring an extensible algebraic notation for the Lisp programming language. It was designed for MACLISP by Vaughan Pratt and subsequently ported to Common Lisp.

<span class="mw-page-title-main">Gary Miller (computer scientist)</span> American computer scientist

Gary Lee Miller is a professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 2003 he won the ACM Paris Kanellakis Award for the Miller–Rabin primality test. He was made an ACM Fellow in 2002 and won the Knuth Prize in 2013.

Michael Lawrence Fredman is an emeritus professor at the Computer Science Department at Rutgers University, United States. He earned his Ph.D. degree from Stanford University in 1972 under the supervision of Donald Knuth. He was a member of the mathematics department at the Massachusetts Institute of Technology from 1974 to 1976. and of the Computer Science and Engineering department at the University of California, San Diego until 1992. Among his contributions to computer science are the development of the Fibonacci heap in a joint work with Robert Tarjan, the transdichotomous model of integer computing with Dan Willard, and the proof of a lower bound showing that Θ(n log n) is the optimal time for solving Klee's measure problem in a joint work with Bruce Weide.

Thomas Nathaniel Hibbard was an American mathematician and computer scientist.

David Anthony Klarner was an American mathematician, author, and educator. He is known for his work in combinatorial enumeration, polyominoes, and box-packing.

Jean Vuillemin is a French computer scientist known for his work in data structures and parallel computing. He is a professor of computer science at the École normale supérieure (Paris).

References

  1. ↑ Vaughan Ronald Pratt: Shellsort and Sorting Networks. Garland Publishing, Inc., New York & London, 1979, ISBN   0-8240-4406-1
  2. ↑ "Designers: Vaughan Pratt". Logobook. Archived from the original on 9 August 2020. Retrieved 7 August 2021.
  3. ↑ Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214–220. 1975. Citations, Full-text (requires paid login)
  4. ↑ Donald Knuth, James H. Morris, Jr., and Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323–350. 1977. Citations
  5. ↑ Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (August 1973). "Time bounds for selection" (PDF). Journal of Computer and System Sciences. 7 (4): 448–461. doi: 10.1016/S0022-0000(73)80033-9 .
  6. ↑ Pratt, V.R., Top Down Operator Precedence. Proceedings of the ACM Symposium on Principles of Programming Languages. 1973. pp41-51.
  7. ↑ George J. Carrette A simple Pratt-Parser for SIOD. 1990.
  8. ↑ https://github.com/douglascrockford/JSLint/blob/40e3f73127b56f24a12e5cb091a86d9a24130926/fulljslint.js jslint source code line 2224
  9. ↑ Eric Fischer. Emacs and Other Editors. alt.folklore.computers. November 15, 2000.
  10. ↑ BBC News.Surfing on a matchbox. 1999.
  11. ↑ CNN News. Smallest Web server fits in shirt pocket. 1999.
  12. ↑ "How to Bruise an Integer" Archived 2008-10-07 at the Wayback Machine , Byte, March 1995.
  13. ↑ "Chain Reaction in Pentiums", Vaughan Pratt, 1994. In wdv-notes334, 22 Jan, 1995. Article is formatted from a newsgroup posting: Vaughan Pratt (30 December 1994). ""TECHNICAL: Chain reaction in Pentiums (Was: The Flaw: Pentium-Contaminated Data Persists)"". Newsgroup:  comp.sys.intel. Usenet:   3e097i$952@Radon.Stanford.EDU . Retrieved 3 June 2006.
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.