Michael Rabin

Michael Oser Rabin was born in Breslau, Germany (now Wroclaw, Poland) in 1931. He emigrated to Palestine in 1935 and attended Hebrew University in Jerusalem. He received his Ph.D. in mathematics from Princeton University. He later taught at Princeton University. In 1958 he moved to the Hebrew University in Jerusalem. His early influences included Stephen Kleene's book Introduction to Metamathematics and the work of Alan Turing.

Among his other accomplishments, Rabin is known for his fundamental 1959 paper with Dana Scott, which constructed a firm mathematical basis for the theory of finite automata, and introduced the concept of nondeterminism. For this paper, along with other achievements, Rabin was a co-winner of the 1976 ACM Turing award, computer science's highest award.

Currently, Rabin divides his time between positions at Harvard University and Hebrew University of Jerusalem.

Sources

  1. Dennis Shasha and Cathy Lazere, Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists, Copernicus, 1995.
  2. M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Research 3 (1959), 115-125.
  3. M. O. Rabin, Complexity of computations, Communications of the ACM 20 (1977), 625-633.

Back to Theory of Computing Hall of Fame Main Page
Back to CS 462 home page

cs462@descartes
September 10 1997