|
Robert McNaughton Pour les articles homonymes, voir McNaughton.  Ne doit pas être confondu avec Robert MacNaughton. Robert McNaughton 
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èreIl 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 scientifiquesSes 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)
Notes et références
Bibliographie
Liens externes
|
