Robert McNaughton

Pour les articles homonymes, voir McNaughton.

Ne doit pas être confondu avec Robert MacNaughton.

Robert McNaughton

Biographie

Naissance	1924
Décès	5 juin 2014 Troy
Nationalité	américaine
Formation	Université Harvard Université Columbia
Activités	Mathématicien, informaticien

Autres informations

A travaillé pour	Université de Pennsylvanie Institut polytechnique Rensselaer
Directeur de thèse	Willard Van Orman Quine
Distinction	Louis E. Levy Medal of the Franklin Institute

modifier - modifier le code - modifier Wikidata

Robert Forbes McNaughton, Jr., né en 1924 et mort le 5 juin 2014 à Troy, État de New York à l'âge de 90 ans^[1], est un mathématicien, logicien, et informaticien théoricien américain. Il est un pionnier de la théorie des automates, et auteur de contributions fondamentales en plusieurs domaines d'informatique théorique, comme les langages formels, les grammaires et systèmes de réécriture, la combinatoire des mots.

Carrière

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.

Contributions scientifiques

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].

Publications (sélection)

• 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

Notes et références

Bibliographie

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

Liens externes

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

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

• Portail des mathématiques
• Portail de l'informatique théorique
• Portail de la logique