Wikipédia

Alan Cobham (informaticien)

mathématicien américain
Page d’aide sur l’homonymie

Pour les articles homonymes, voir Alan Cobham.

Alan Belmont Cobham, né le [1] à San Francisco en Californie, et mort le à Middletown au Connecticut[1],[2], est un mathématicien et informaticien théoricien américain. Il est connu[3] 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é.

Alan Cobham
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Décès
Voir et modifier les données sur Wikidata (à 83 ans)
MiddletownVoir et modifier les données sur Wikidata
Nationalité
Activités
Autres informations
A travaillé pour
Contributions principales
  • The intrinsic computational difficulty of functions
  • On the base-dependence of sets of numbers recognizable by finite automata
  • Uniform tag sequences

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

Biographie modifier

Entre 1940 et 1945, la famille d'Alan Cobham s'installe dans le Bronx, où Alan fréquent la Fieldston School (en). 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 « Operations Evaluation Group » 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[4]. 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 [2].

Travaux modifier

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 « The intrinsic computational difficulty of functions » 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 « On the base-dependence of sets of numbers recognizable by finite automata » de 1969 il montre que si un même ensemble de nombres est reconnaissable en deux bases multiplicativement indépendantes[5], 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 « The proof is correct, long, and hard. Il is a challenge to find a more reasonable proof of this fine theorem ». 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[6]. Une généralisation aux substitutions est donnée par Fabien Durand[7].

L'autre article sur le même sujet date de 1972 : « Uniform tag sequences ». 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[1] : « This paper has led to hundreds of others exploring the theory of automatic sequences and generalizing them. »

Publications modifier

Articles modifier

  • [1977] (en) Alan Cobham, « Representation of a word function as the sum of two functions », Mathematical Systems Theory, vol. 11, no 1,‎ , p. 373–377 (DOI 10.1007/BF01768487, MR 0484854)
  • [1972] (en) Alan Cobham, « Uniform tag sequences », Mathematical Systems Theory, vol. 6, nos 1-2,‎ , p. 164–192 (DOI 10.1007/BF01706087, MR 0457011).
  • [1969] (en) Alan Cobham, « On the base-dependence of sets of numbers recognizable by finite automata », Mathematical Systems Theory, vol. 3, no 2,‎ , p. 186–192 (DOI 10.1007/BF01746527, MR 0250789) (Reviewer: J. Hartmanis)
  • [1963] (en) Alan Cobham, « Some remarks concerning theories with recursively enumerable complements », The Journal of Symbolic Logic, vol. 28, no 01,‎ , p. 72–74 (DOI 10.2307/2271337, MR 173629, zbMATH 0124.25002) (Reviewer: P. Lorenzen)
  • [1956] (en) Alan Cobham, « Reduction to a symmetric predicate », The Journal of Symbolic Logic, vol. 21, no 01,‎ , p. 56–59 (DOI 10.2307/2268487, MR 0078311) (Reviewer: P. Lorenzen)
  • [1954] (en) Alan Cobham, « Priority Assignment in Waiting Line Problems », Journal of the Operations Research Society of America, vol. 2, no 1,‎ , p. 70–76 (DOI 10.1287/opre.2.1.70) - Correction Operations Research vol 3 n° 4 p. 547 (1955)

Conférences modifier

  • [1968] (en) Alan Cobham, « On the Hartmanis-Stearns problem for a class of tag machines », 9th Annual Symposium on Switching and Automata Theory, IEEE Computer Society,‎ , p. 51–60 (DOI 10.1109/SWAT.1968.20)
  • [1968] (en) A. Cobham, « Functional equations for register machines », Proccedings of the Hawaii International Conference on System Sciences,‎ , p. 10-13
  • [1966] (en) Alan Cobham, « The recognition problem for the set of perfect squares », 7th Annual Symposium on Switching and Automata Theory, IEEE Computer Society,‎ , p. 78–87 (DOI 10.1109/SWAT.1966.30)[8]
  • [1965] (en) Alan Cobham, « The intrinsic computational difficulty of functions », Studies in logic and the foundations of mathematics, North-Holland « Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.) »,‎ , p. 24–30 (MR 0207561, SUDOC 005411750) (Reviewer: J. R. Büchi)
  • [1961] (en) A. Cobham, R. Fridshal et J. H. North, « An application of linear programming to the minimization of Boolean functions », 2nd Annual Symposium on Switching Circuit Theory and Logical Design, IEEE Computer Society,‎ , p. 3–9 (DOI 10.1109/FOCS.1961.5)

Notes et références modifier

  1. ↑ a b et c Shallit 2010.
  2. ↑ a et b Alan Cobham : An Appreciation.
  3. ↑ CiteSeerX dénombre 1 813 articles pour le mot clé « Cobham ».
  4. ↑ Frana 2012.
  5. ↑ Deux entiers a et b sont multiplicativement dépendant s'il existe des entiers positifs n et m tels que an=bm.
  6. ↑ Bruyère 2010.
  7. ↑ Durand 2011.
  8. ↑ Commentaire sur : Early Early Automata Theory at IBM

Bibliographie modifier

  • « Alan Cobham: An Appreciation », Formal power series, sur derivativesinvesting.net, (consulté le ).
  • Jeffrey Shallit, « Alan Cobham », Recursivity, sur recursed.blogspot.fr, (consulté le ).
  • (en) Philip L. Frana, « An interview with Stephen A. Cook », Communications of the ACM, vol. 55, no 1,‎ , p. 41 (DOI 10.1145/2063176.2063193).
  • Véronique Bruyère, « Around Cobham's theorem and some of its extensions », Dynamical Aspects of Automata and Semigroup Theories, Satellite Workshop of Highlights of AutoMathA, (consulté le ) (présentation)
  • (en) Fabien Durand, « Cobham's theorem for substitutions », Journal of the European Mathematical Society, vol. 13, no 6,‎ , p. 1797–1812 (DOI 10.4171/JEMS/294, arXiv 1010.4009, lire en ligne).

Article lié modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Alan_Cobham_(informaticien)&oldid=206461986 ».