Alan Cobham (informaticien)
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é.
| Naissance | |
|---|---|
| Décès |
(Ă 83 ans) Middletown |
| Nationalité | |
| Activités |
| A travaillé pour |
|---|
|
Biographie
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
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
Articles
- [1986] (en) Alan Cobham, « Stochastic automata with large state spaces and low rank », Linear Algebra and its Applications, vol. 75,‎ , p. 57–66 (DOI 10.1016/0024-3795(86)90181-3, MR 0825399, lire en ligne).
- [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
- [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
- Shallit 2010.
- Alan Cobham : An Appreciation.
- CiteSeerX dénombre 1 813 articles pour le mot clé « Cobham ».
- Frana 2012.
- Deux entiers a et b sont multiplicativement dépendant s'il existe des entiers positifs n et m tels que an=bm.
- Bruyère 2010.
- Durand 2011.
- Commentaire sur : Early Early Automata Theory at IBM
Bibliographie
- « 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).