Early Automata Theory
Mathematics Accomplishment | 1957 - 1966
Where the work was done: IBM T.J. Watson Research Center
What we accomplished: As outlined in the details below, IBM had multiple contributions to the early development of automata theory used in parsing, artificial intelligence, and elsewhere (Rabin, pictured).
- Finite Automata and Their Decision Problems by Michael Rabin and Dana Scott in April 1959 IBM Journal.
- Written while Rabin and Scott were at IBM in the summer of 1957. Among other things, this paper introduces the notion of non-deterministic finite automata and shows there is an equivalent deterministic one.
- The Recognition Problem for the Set of Perfect Squares by Alan Cobham in the October 1966 IEEE Symposium on Automata and Switching Theory.
- The paper addresses the issue of determining whether an integer is a perfect square and provides an algorithm, which in terms of memory requirements, "is asymptotically at least within a factor of four of being the best possible square-recognizing device." In developing this algorithm, Cobham developed Crossing Sequence arguments.
Image credit: ACM