Jump to content

Alan Cobham (mathematician)

From Wikipedia, the free encyclopedia
Alan Belmont Cobham
Born(1927-11-04)November 4, 1927
DiedJune 28, 2011(2011-06-28) (aged 83)
NationalityAmerican
OccupationTheoretical computer scientist
Known forDefining the class P, Cobham's thesis, Cobham's theorem, inventing priority queues, writing a program to play contract bridge

Alan Belmont Cobham (4 November 1927 – 28 June 2011)[1] was an American mathematician and computer scientist known for (with Jack Edmonds and Michael O. Rabin) inventing the notion of polynomial time and the complexity class P,[2][B] for Cobham's thesis stating that the problems that have practically usable computer solutions are characterized by having polynomial time,[3][B] and for Cobham's theorem on the sets of numbers that can be recognized by finite automata.[4][C] He also did foundational work on automatic sequences,[5][D] invented priority queues and studied them from the point of view of queueing theory,[6][A] and wrote a program for playing contract bridge that was at the time (in the mid-1980s) one of the best in the world.[7]

Cobham was a student at Oberlin College, the University of Chicago, the University of California, Berkeley, and the Massachusetts Institute of Technology, but did not complete a doctorate. He became an operations researcher for the United States Navy, a researcher for IBM Research at the Thomas J. Watson Research Center, and a professor and founding department chair of the computer science department at Wesleyan University.[1]

Selected publications

[edit]
A.
Cobham, Alan (February 1954). "Priority assignment in waiting line problems". Journal of the Operations Research Society of America. 2 (1): 70–76. doi:10.1287/opre.2.1.70.
B.
Cobham, Alan (1965). "The intrinsic computational difficulty of functions". In Bar-Hillel, Yehoshua (ed.). Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland. pp. 24–30. MR 0207561.
C.
Cobham, Alan (June 1969). "On the base-dependence of sets of numbers recognizable by finite automata". Mathematical Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527. MR 0250789. S2CID 19792434.
D.
Cobham, Alan (March 1972). "Uniform tag sequences". Mathematical Systems Theory. 6 (1–2): 164–192. doi:10.1007/BF01706087. MR 0457011. S2CID 28356747.

References

[edit]
  1. ^ a b Shallit, Jeffrey (March 31, 2010). "Alan Cobham". Recursivity. Shallit, Jeffrey (November 12, 2014). "Alan Cobham: An Appreciation". Recursivity.
  2. ^ Kozen, Dexter C. (2006). Theory of Computation. Springer. p. 4. ISBN 978-1-84628-297-3.
  3. ^ Ausiello, Giorgio (2018). The Making of a New Science: A Personal Journey Through the Early Years of Theoretical Computer Science. Springer. p. 43. ISBN 978-3-319-62680-2.
  4. ^ Durand, Fabien; Rigo, Michel (2010). "On Cobham's Theorem" (PDF). In Pin, J.-É. (ed.). Automata: from Mathematics to Applications. European Mathematical Society.
  5. ^ Rowland, Eric (March 2015). "What is...an automatic sequence?" (PDF). Notices of the American Mathematical Society. 62 (3): 274–276. doi:10.1090/noti1218.
  6. ^ Miller, Rupert G. Jr. (1960). "Priority queues". Annals of Mathematical Statistics. 31: 86–103. doi:10.1214/aoms/1177705990. MR 0120688.
  7. ^ Truscott, Alan (October 7, 1984). "Bridge: Playing against computers". The New York Times.


Flag of United StatesScientist icon

This article about an American mathematician is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Alan_Cobham_(mathematician)&oldid=1235289165"