Vaughan Pratt

Vaughan Ronald Pratt (born 1944), a Professor Emeritus at Stanford University, was one of the earliest pioneers in the field of computer science. Publishing since 1969, Pratt has made innumerable 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. A pattern of applying models from diverse areas of mathematics such as geometry, linear algebra, abstract algebra, and especially mathematical logic to computer science pervades his work.

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.ref|1 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.ref|2 Along with Blum, Floyd, Rivest, and Tarjan, he described the first worst-case optimal selection algorithm.ref|3

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 parsingref|4. His parser is sometimes called a "Pratt parser"ref|5 and has been used in later systems, such as MACSYMA. He also implemented a TECO-based text editor named "DOC", which was later renamed to "ZED".ref|6

History

Raised in Australia, 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.

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

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.ref|9ref|10

In 1999, Pratt built the world's smallest (at the time) web server — it was the size of a matchbox.ref|7ref|8

Pratt became professor emeritus at Stanford in 2000.

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 with the Association for Computing Machinery and is on the Editorial Board of three major mathematics journals. He is also the Chairman and CTO of [http://www.tiqit.com/ TIQIT Computers, Inc.] .

References

Vaughan Pratt. Every prime has a succinct certificate. "SIAM Journal on Computing", vol.4, pp.214–220. 1975. [http://citeseer.ist.psu.edu/context/39245/0 Citations] , [http://locus.siam.org/SICOMP/volume-04/art_0204018.html Full-text] (requires paid login)

Donald Knuth, James H. Morris, Jr., and Vaughan Pratt. Fast pattern matching in strings. "SIAM Journal on Computing", 6(2):323–350. 1977. [http://citeseer.ist.psu.edu/context/23820/0 Citations] .

M. Blum, R.W. Floyd, V. Pratt, R. Rivest and R. Tarjan, "Time bounds for selection," "J. Comput. System Sci". 7 (1973), pp.448–461.

Pratt, V.R., Top Down Operator Precedence. Proceedings of the ACM Symposium on Principles of Programming Languages. 1973. pp41-51.

George J. Carrette [http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/scheme/code/parsing/pratt/pratt.scm A simple Pratt-Parser] for SIOD. 1990.

Eric Fischer. [http://groups.google.com/group/alt.folklore.computers/msg/ee505c7d0b1d0c1e?dmode=source Emacs and Other Editors] . alt.folklore.computers. November 15, 2000.

BBC. [http://news.bbc.co.uk/2/hi/science/nature/276762.stm Surfing on a matchbox] . 1999.

CNN. [http://www.cnn.com/TECH/computing/9902/11/smallweb.idg/ Smallest Web server fits in shirt pocket] . 1999.

[http://byte.com/art/9503/sec13/art2.htm "How to Bruise an Integer"] , Byte, March 1995.

[http://www.khd-research.net/Notes/wdv-notes_334.pdf "Chain Reaction in Pentiums"] , Vaughan Pratt, 1994. In wdv-notes334, 22 Jan, 1995. Article is formatted from a newsgroup posting: cite newsgroup
title = "TECHNICAL: Chain reaction in Pentiums (Was: The Flaw: Pentium-Contaminated Data Persists)"
author = Vaughan Pratt
date = 1994-12-30
newsgroup = comp.sys.intel
id = 3e097i$952@Radon.Stanford.EDU
url = http://groups.google.com/group/comp.sys.intel/msg/797cf26bcfb4f67a?dmode=source
accessdate = 2006-06-03 .

External links

*
* [http://boole.stanford.edu/pratt.html Faculty home page at Stanford University]
* [http://boole.stanford.edu/abstracts.html Abstract page] , with full-text downloads of many of Pratt's publications.