Robert McNaughton

Il obtient un Ph. D. à l'université Harvard sous la direction de Willard Van Orman Quine en 1951 avec une thèse ayant pour titre On Establishing the Consistency of Systems[2]. Après avoir enseigné à la Moore School of Electrical Engineering de l'université de Pennsylvanie, il rejoint l'Institut polytechnique Rensselaer, où il reste jusqu'à sa retraite.

Ses premières contributions sont en théorie des ensembles, souvent en collaboration avec Wang Hao. Il contribue aussi à divers aspects de la philosophie des mathématiques. Après avoir enseigné la philosophie pendant six ans, il se tourne vers l'informatique[3].

Son premier travail fondamental est l'article de 1960[4], avec son étudiant d'alors Hisao Yamada, encore à l'université de Pennsylvanie. Il contient l'algorithme de McNaughton et Yamada reproduit dans les manuels, et aussi une construction inverse des automates à partir d'une expression, moins souvent citée.

Il s'intéresse à la classification des langages rationnels sous divers aspects : combinatoire, algébrique, logique[5]. Le livre coécrit avec Seymour Papert[6] Counter-free automata et paru en 1971 traite de manière unifiée la classe des langages sans étoile, en rapport avec la logique du premier ordre, les automates sans permutations et les langages dont le monoïde syntaxique est apériodique, équivalence démontrée par Schützenberger quelques années auparavant.

McNaughton est probablement le plus connu par ses recherches sur les automates sur les mots infinis. Dans son travail fondamental de 1966[7] Testing and Generating Infinite Sequences by a Finite Automaton, il démontre le premier résultat fondamental de cette théorie, à savoir que la déterminisation d'un automate de Büchi non déterministe se fait par une transformation en un automate de Muller déterministe[5].

D'autres domaines de recherche où McNaughton a contribué sont la théorie des jeux, les systèmes de réécriture, où il introduit, avec Paliath Narendran et Friedrich Otto, le concept de langage de Church-Rosser[8] - [5].

• Robert McNaughton et Hisao Yamada, « Regular expressions and state graphs for automata », IRE Trans. Electronic Computers, vol. EC-9, n^o 1,‎ janvier 1960, p. 39-47 (DOI 10.1109/TEC.1960.5221603).
• Robert McNaughton, Elementary computability, formal languages, and automata, Englewood Cliffs, N.J., Prentice-Hall, 1982, xvi+400 (ISBN 0-13-253500-9, OCLC 264353810).
• Robert McNaughton, Paliath Narendran et Friedrich Otto, « Church-Rosser Thue systems and formal languages », Journal of the ACM, vol. 35, n^o 2,‎ 1988, p. 324-344
• Robert McNaughton et Seymour Papert, Counter-free automata, M.I.T. Press, coll. « MIT Research monographs » (n^o 65), 1971, 163 p. (ISBN 9780262130769)
• Wang Hao et Robert McNaughton, Les systèmes axiomatiques de la théorie des ensembles, Paris et Louvain, Gauthier-Villars et E. Nauwelaerts, coll. « Collection de logique mathématiques, série A », 1953, 54 p. (ISSN 0530-7554, OCLC 422396010, SUDOC 006780474)
• Robert McNaughton, « Testing and Generating Infinite Sequences by a Finite Automaton », Information and Control, vol. 9, n^o 5,‎ 1966, p. 521-530

• John Corcoran, Paliath Narendran et Wolfgang Thomas, « Obituary Robert McNaughton 1924 – 2014 », Bulletin de l’EATCS, n^o 114,‎ octobre 2014 (lire en ligne)

• Robert McNaughton Harvard University
• Ressources relatives à la recherche :
  • (en) Digital Bibliography & Library Project
  • (en) Mathematics Genealogy Project
• Notices d'autorité :

  • VIAF
  • ISNI
  • BnF (données)
  • IdRef
  • LCCN
  • GND
  • Pays-Bas
  • Israël
  • NUKAT
  • Norvège
  • Lettonie
  • WorldCat