• go to J. H. Wilkinson 's profile page
  • go to Richard E Stearns's profile page
  • go to Barbara Liskov's profile page
  • go to Joseph Sifakis's profile page
  • go to Leslie Lamport's profile page
  • go to Pat Hanrahan's profile page
  • go to Leslie G Valiant's profile page
  • go to Maurice V. Wilkes's profile page
  • go to Juris Hartmanis's profile page
  • go to Edwin Catmull's profile page
  • go to Kristen Nygaard 's profile page
  • go to Richard W. Hamming's profile page
  • go to Martin Hellman 's profile page
  • go to Yoshua Bengio's profile page
  • go to Yann LeCun's profile page
  • go to Sir Tim Berners-Lee's profile page
  • go to Shafi Goldwasser 's profile page
  • go to Edsger W. Dijkstra's profile page
  • go to Alfred V Aho's profile page
  • go to Dennis M. Ritchie 's profile page
  • go to Peter Naur's profile page
  • go to John Cocke 's profile page
  • go to Amir Pnueli's profile page
  • go to Jeffrey D Ullman's profile page
A.M. TURING AWARD WINNERS BY...

Michael O. Rabin DL Author Profile link

United States – 1976
Short Annotated Bibliography
  1. Rabin, Michael O. and Dana Scott, “Finite Automata and Their Decision Problems,” IBM Journal of Research and Development, Vol. 3, Num. 2, 1959, pp. 114-125. Russian translation: “Konechnye avtomaty i zadachi ikh razresheniya,” Kiberneticheskii sbornik, vol. 4 (1962), pp. 58-91. Reprinted in: Moore E. F. (editor), Sequential Machines, Selected Papers, Addison Wesley Publishing Company, Reading, MA (1964), pp. 63-92. This paper contains the research work on nondeterministic automata for which the two authors received the 1976 Turing Award.
  2. Rabin, Michael O., "Degree of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets," Technical Report No. 2, O.N.R., Hebrew University, Jerusalem, 1960. This paper was inspired by the “spies and guards” problem from John McCarthy.
  3. Rabin, Michael O. (1980), "Probabilistic algorithm for testing primality," Journal of Number Theory, Vol. 12, Num. 1, pp. 128–138. This paper describes the randomized algorithm developed by Miller and Rabin for primality testing
  4. Rabin, Michael O. and J. O. Shallit, “Randomized Algorithms in Number Theory,” Communications on Pure and Applied Mathematics, Vol. 39, Num. S1, 196, pp. S239-S256. In this work the two authors use the randomized algorithm for Lagrange’s four-square as an illustration of their approach.