*mcnaught@cs.rpi.edu*

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.

- "Buchi's Sequential Calculus," in The Collected Works of J. Richard Buchi, Saunders MacLane and Dirk Siefkes, eds. Springer-Verlag, 1990, pp. 382-397.
- "The development of formal language theory since 1956," Int. Jour. Foundations of Computer Science, Vol. 1 (1990), pp. 355-368.
- "A polynomial-time algorithm for the local testability problem of deterministic finite automata," IEEE Trans. Computers, Vol. 40 (1991), pp. 1087-1093 (with Sam M. Kim and Robert McCloskey).
- "Infinite games played on finite graphs," Annals of Pure and Applied Logic, Vol. 65 (1993), pp. 149-184.
- "Computing the order of a locally testable automaton," SIAM J. Comput., Vol. 23 (1994), pp. 1193-1215 (with Sam M. Kim).
- "Contributions of Ronald V. Book to the theory of string-rewriting systems," to appear in Theoretical Computer Science, 1998 or later. Now available at http://www.cs.rpi.edu/research/tr.html.
- "The finiteness of finitely presented monoids," to appear in Theoretical Computer Science, 1998 or later. Now available at http://www.cs.rpi.edu/research/tr.html.
- "Semi-Thue systems with an inhibitor," submitted for publication in April 1998. Now available at http://www.cs.rpi.edu/research/tr.html.