 |
 |
Finite automata and their decision problems
|  |
 |
 |
 |
by M. O. Rabin and D. Scott |
 |
|
|  |
 |  |  |
|
|
|
|
IBM Journal of Research and Development, Volume 3, Issue 2, pp. 114-125 (1959).
|
|
|
In this classic paper, Rabin and Scott introduced the concept of nondeterministic machines, which play a key role in computational complexity theory, and in the description of complexity classes P and NP in particular. For this seminal contribution, which has been a continuous source of inspiration for subsequent work in this field, the authors received the ACM A. M. Turing Award in 1976.
|
|
|
See Michael O. Rabin's and Dana S. Scott's ACM A. M. Turing Award (1976).
|