Vaughan Pratt | |
|---|---|
 | |
| Born | Vaughan Ronald Pratt (1944-04-12)April 12, 1944 (age 80) 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 |
| Doctoral students | |
| Website | boole |
Vaughan Pratt (born April 12, 1944) is aProfessor Emeritus atStanford University, who was an early pioneer in the field ofcomputer science. Since 1969, Pratt has made several contributions to foundational areas such assearch algorithms,sorting algorithms, andprimality testing. More recently, his research has focused on formal modeling ofconcurrent systems andChu spaces.
Raised in Australia and educated atKnox Grammar School, where he wasdux in 1961, Pratt attendedSydney University, where he completed his masters thesis in 1970, related to what is now known asnatural 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 advisorDonald Knuth. His thesis focused on analysis of theShellsort sorting algorithm andsorting networks.[1]
Pratt was an assistant professor atMIT (1972 to 1976) and then associate professor (1976 to 1982). In 1974, working in collaboration with Knuth andJames H. Morris, Pratt completed and formalized work he had begun in 1970 as a graduate student atBerkeley; the coauthored result was theKnuth–Morris–Pratt pattern matching algorithm. In 1976, he developed the system ofdynamic logic, amodal logic of structured behavior.
He went on sabbatical from MIT toStanford (1980 to 1981), and was appointed a full professor at Stanford in 1981.
Pratt directed theSUN workstation project at Stanford from 1980 to 1982. He contributed in various ways to the founding and early operation ofSun 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 theSun Microsystems logo,[2] which featuresfour interleaved copies of the word "sun"; it is anambigram.
Pratt became professor emeritus at Stanford in 2000.
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 theprimality testing problem in the complexity classNP and providing the first strong evidence that the problem is notco-NP-complete.[3]TheKnuth–Morris–Pratt algorithm, which Pratt designed in the early 1970s together with fellow Stanford professorDonald Knuth and independently fromMorris, is still the most efficient generalstring searching algorithm known today.[4] Along withBlum,Floyd,Rivest, andTarjan, he describedmedian of medians, the first worst-case optimalselection algorithm.[5]
Pratt built some useful tools. In 1976, he wrote anMIT AI Lab working paper aboutCGOL, an alternative syntax forMACLISP 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 asMACSYMA.Douglas Crockford also used it as the underlying parser forJSLint.[8] Pratt also implemented aTECO-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]
Pratt was credited in a 1995Byte magazine article for proposing that thePentium 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 theAssociation for Computing Machinery and is on the editorial board of three major mathematics journals. He was also the founder, chairman, and CTO ofTIQIT Computers, Inc. for the ten years prior to when it closed its doors in 2010.
