Early Automata Theory       

Mathematics Accomplishment | 1957 - 1966

IBM researchers: Michael Rabin (Turing Award Winner), Dana Scott (Turing Award Winner), Alan Cobham

Where the work was done: IBM T.J. Watson Research Center

What we accomplishedAs 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).

Related links

  • 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