Alan Belmont Cobham, né le . à San Francisco en Californie, et mort le à Middletown au Connecticut., est un mathématicien et informaticien théoricien américain. Il est connuCiteSeerX dénombre pour le mot clé « Cobham ». pour ses travaux conduisant à la définition de la classe de complexité P, et la thèse de Cobham, et à la définition et l'étude de ce qui est appelé maintenant les suites automatiques, écrits qui ont eu un impact prolongé.

Biographie Entre 1940 et 1945, la famille d'Alan Cobham s'installe dans le Bronx, où Alan fréquent la . Il est ensuite élève au Oberlin College, puis étudie à l'Université de Chicago. Au début des années 1950, il travaille quelque temps au de l'United States Navy. Il étudie ensuite à Berkeley et au MIT, mais n'a jamais terminé un Ph. D. Il préfère aller travailler chez IBM.. Depuis le début des années 1960, et jusqu'en 1984, Cobham est chercheur au Thomas J. Watson Research Center de IBM à Yorktown Heights. C'est là qu'il produit les articles qui ont fait sa renommée.

Cobham a également réalisé chez IBM un programme de jeu de bridge qui était, à l'époque, l'un des meilleurs programmes de bridge au monde, et a été mentionné dans un article du New York Times du . À l'automne 1984, Cobham quitte IBM pour la direction du département d'informatique naissant de l'Université Wesleyenne à Middletown, dans le Connecticut, où il travaille jusqu'à sa retraite, le .

Travaux

Cobham est renommé pour plusieurs travaux. D'une part, il était l'un des premiers chercheurs à considérer la classe de complexité P dans son article de 1965, connu maintenant sous le titre de thèse de Cobham.

D'autre part, il s'intéresse aux ensembles d'entiers que l'on peut reconnaître par un automate fini à partir de leur écriture dans une base donnée. Dans son article de 1969 il montre que si un même ensemble de nombres est reconnaissable en deux bases multiplicativement indépendantesDeux entiers a et b sont multiplicativement dépendant s'il existe des entiers positifs n et m tels que a=b., alors cet ensemble est composé de constante et de suites arithmétiques. Cet énoncé figure sous le nom de « théorème de Cobham » dans le livre d'Allouche et Shallit par exemple ou dans le traité d'Eilenberg qui donne sans preuve; il dit . Depuis, de nombreuses études ont porté sur ce théorème. Un court aperçu est dans la présentation de Véronique Bruyère.. Une généralisation aux substitutions est donnée par Fabien Durand..

L'autre article sur le même sujet date de 1972 : . Il a donné naissance à ce qu'on appelle maintenant des suites automatiques qui font l'objet du livre d'Allouche et Shallit. Comme dit Shallit :

Publications Articles

.

.

(Reviewer: J. Hartmanis)

(Reviewer: P. Lorenzen)

(Reviewer: P. Lorenzen)

- Correction Operations Research vol 3 n° 4 (1955)

Conférences

Commentaire sur : Early Early Automata Theory at IBM

(Reviewer: J. R. Büchi)

Notes et références

Bibliographie . . . (présentation) .

Article lié Système de tague Théorème de Cobham Suite automatique

Catégorie:Informaticien américain Catégorie:Théoricien des nombres Catégorie:Personnalité en informatique théorique Catégorie:Naissance en novembre 1927 Catégorie:Naissance à San Francisco Catégorie:Décès en juin 2011 Catégorie:Décès à Middletown (Connecticut) Catégorie:Décès à 83 ans