Vaughan Ronald Pratt

From Wikipedia, the free encyclopedia

Vaughan Ronald Pratt, 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.^[1] The Knuth-Morris-Pratt algorithm, which Pratt designed in 1977 together with fellow Stanford professor Donald Knuth and independently from Morris, is still the most efficient general string searching algorithm known today.^[2] Along with Blum, Floyd, Rivest, and Tarjan, he described the first worst-case optimal selection algorithm.^[3]

[edit] 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 came 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.

He coauthored the Knuth-Morris-Pratt pattern matching algorithm in 1974, and developed the system of dynamic logic, a modal logic of structured behavior, in 1976. He directed the Sun workstation project at Stanford from 1980 to 1982 and went on to help found Sun Microsystems. He also designed the Sun logo, which features four interleaved copies of the word "sun"; it is an ambigram.

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 TIQIT Computers, Inc..

Pratt's Erdős number is two due to his collaboration with Frances Yao.

[edit] References

↑ Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214–220. 1975. Citations, 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. Citations.

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