IBM®
Skip to main content
    Country/region [change]    Terms of use
 
 
 
    Home    Products    Services & solutions    Support & downloads    My account    

IBM Technical Journals

Special report: Celebrating 50 years of the IBM Journals
All topics > Computing Methodologies >

Finite automata and their decision problems

Award plaque by M. O. Rabin
and D. Scott

Finite automata are considered in this paper as instruments for classifying finite tapes. Each one-tape automaton defines a set of tapes, a two-tape automaton defines a set of pairs of tapes, et cetera. The structure of the defined sets is studied. Various generalizations of the notion of an automaton are introduced and their relation to the classical automata is determined. Some decision problems concerning automata are shown to be solvable by effective algorithms; others turn out to be unsolvable by algorithms.

Originally published:

IBM Journal of Research and Development, Volume 3, Issue 2, pp. 114-125 (1959).

Significance:

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.

Comments:

See Michael O. Rabin's and Dana S. Scott's ACM A. M. Turing Award (1976).


    About IBMPrivacyContact