Robert McNaughton

Page d’aide sur l’homonymie

Pour les articles homonymes, voir McNaughton.

Page d’aide sur l’homonymie

Ne doit pas être confondu avec Robert MacNaughton.

Robert McNaughton
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Décès
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Directeur de thèse
Distinction

modifier - modifier le code - modifier WikidataDocumentation du modèle

Robert Forbes McNaughton, Jr., né en 1924 et mort le à 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, no 1,‎ , p. 39-47 (DOI 10.1109/TEC.1960.5221603).
  • Robert McNaughton, Elementary computability, formal languages, and automata, Englewood Cliffs, N.J., Prentice-Hall, , 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, no 2,‎ , p. 324-344
  • Robert McNaughton et Seymour Papert, Counter-free automata, M.I.T. Press, coll. « MIT Research monographs » (no 65), , 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 », , 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, no 5,‎ , p. 521-530

Notes et références

  1. ↑ Faire-part de décès.
  2. ↑ (en) « Robert Forbes McNaughton », sur le site du Mathematics Genealogy Project.
  3. ↑ Sur sa page personnelle, il est indiqué que « His career switch was due to the lean job market more than anything else ».
  4. ↑ McNaughton et Yamada 1960.
  5. ↑ a b et c Corcoran, Narendran, Thomas, Obituary.
  6. ↑ McNaughton et Papert 1971.
  7. ↑ McNaughton 1966.
  8. ↑ McNaughton, Narendran et Otto 1988.

Bibliographie

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

Liens externes