Robert McNaughton
Emeritus Professor
Ph.D., Harvard University
Automata theory, formal languages, combinatorics of words

McNaughton entered computer science in the 1950s after teaching philosophy for six years. His career switch was due to the lean job market more than anything else. Today, however, his training in philosophy holds him in good stead.

McNaughton, who is author of the textbook Elementary Computability, Formal Languages and Automata published by Prentice-Hall, is now looking at problems in the combinatorics of words, a branch of formal languages. Formal languages deal with symbolic logic and computer languages as opposed to the natural languages used in human speech and general-purpose writing.

His research is being coordinated with computer scientists formerly at the GE Research and Development Center in nearby Niskayuna, New York. This group at GE was called the Theorem Proving Group. Members of this group are now in the Computer Science Department at the University at Albany and in the Computer Science Department at RPI. Their research was concerned with looking at formal linguistic systems for the sake of carrying through proofs on the machine. For example, they have looked at ways to improve the efficiency of Thue systems, a linguistic method developed by Norwegian logician Axel Thue in 1914. Thue systems are useful for computation because they replace strings (connected characters) with other strings, carrying through a rather basic kind of computer operation.

On January 28, 2003, McNaughton presented a seminar titled At the Borderline of Number Theory and Computational Geometry Theory to honor the memory of Professor Edith Luchins. Copies of his talk are available in pdf and postscript.


Faculty and Their Research