Andrzej Ehrenfeucht
| Naissance | |
|---|---|
| Nationalités | |
| Formation |
Université de Varsovie Lycée Nicolas-Copernic de Łódź (d) |
| Activités |
| A travaillé pour | |
|---|---|
| Membre de | |
| Directeurs de thèse |
Andrzej Mostowski, Andrzej Włodzimierz Mostowski (d) |
| Site web |
Andrzej Ehrenfeucht (né le à Vilnius) est un mathématicien et informaticien théoricien américain d'origine polonaise. Il travaille principalement dans les domaines de logique mathématique, combinatoire et bio-informatique.
Biographie scientifique[modifier | modifier le code]
Ehrenfeucht étudie les mathématiques à l'université de Varsovie et soutient en 1961[1] une thèse sous la direction d'Andrzej Mostowski à l'institut de mathématiques de l'Académie polonaise des sciences[2],[3]. De 1961 à 1965 il est professeur assistant à Varsovie, avec un séjour à Berkeley; à partir de 1965, il est professeur assistant à Stanford puis à l'université de Californie à Los Angeles. Depuis 1971, il est d'abord professeur associé, puis professeur titulaire d'informatique à l'université du Colorado à Boulder et depuis 2006 « distinguished professor » de l’université[4],[1].
Ehrenfeucht travaille en logique mathématique, théorie des jeux et en théorie des modèles. Il est connu pour l'invention de la technique du jeu d'Ehrenfeucht-Fraïssé avec Roland Fraïssé qui permet de démontrer l'équivalence élémentaire ou la non-équivalence de structures en théorie des modèles[5].
La suite d'Ehrenfeucht-Mycielski nommée d'après lui et Jan Mycielski, est une suite binaire avec des propriétés pseudo-aléatoires[6].
Ehrenfeucht travaille en algorithmique, notamment en théorie des graphes, en combinatoire des mots, sur les algorithmes de pattern matching et d'apprentissage automatique, sur les langages formels et les théories des équations. Il est connu pour avoir formulé la conjecture, appelée « conjecture d'Ehrenfeucht » qui énoncé que tout sous-ensemble S d'un monoïde libre finiment engendré possède un sous-ensemble fini T avec la propriété que deux morphismes qui coïncident sur T coïncident sur S, conjecture qui a provoqué de nombreux travaux avant d'avoir été prouvée en 1985[7]. Maintenant, la conjecture s'appelle le « théorème de compacité ».
Il travaille aussi en bio-informatique et principalement sur le traitement de l’information par la cellule vivante, où il effectue ses recherches sur la base d'une vaste collaboration interdisciplinaire. Il s'intéresse par ailleurs aussi à la l'enseignement des mathématiques, et est actif dans la formation continue d'enseignants de mathématiques[8].
Parmi ses doctorants, on compte les bio-informaticiens Eugene Myers et David Haussler. Ehrenfeucht est marié avec Ina Tarski, la fille d'Alfred Tarski.
Honneurs et distinctions[modifier | modifier le code]
En 2002 Ehrenfeucht reçoit le « Faculty Research Award » de l'université du Colorado (College of Engineering and Applied Science) et en 2005 le « Boulder Faculty Assembly Award ».
Ehrenfeucht est membre de l'Academia Europaea.
Deux volumes d'hommages ont été publiés en son honneur, le premier pour son 65e anniversaire[1], le deuxième[9] à l'occasion de son 80e anniversaire.
Publications[modifier | modifier le code]
- Andrzej Ehrenfeucht, « An application of games to the completeness problem for formalized theories », Fundamenta Mathematicae, vol. 49, 1960/1961, p. 129–141.
- Andrzej Ehrenfeucht et Jan Mycielski, « A pseudorandom sequence: how random is it? », American Mathematical Monthly, vol. 99, , p. 373.
- Patricia Baggett et Andrzej Ehrenfeucht, Breaking Away from the Math Book : Creative Projects for Grades K-6, Rowman & Littlefield Education, , 175 p. (ISBN 978-1-56676-299-1).
- Andrzej Ehrenfeucht, Tero Harju et Grzegorz Rozenberg, The Theory of 2-structures : A Framework for Decomposition and Transformation of Graphs, World Scientific, , 290 p. (ISBN 978-981-02-4042-4, lire en ligne).
- Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David M. Prescott et Grzegorz Rozenberg, Computation in Living Cells : Gene Assembly in Ciliates, Springer Science & Business Media, , 202 p. (ISBN 978-3-540-40795-9, lire en ligne).
- (en) Andrzej Mostowski, Andrzej Ehrenfeucht, V. Wiktor Marek et Marian Srebrny, Andrzej Mostowski and Foundational Studies, Amsterdam, IOS Press, , 447 p. (ISBN 978-1-58603-782-6, lire en ligne)
Bibliographie[modifier | modifier le code]
- Volumes d'hommages
- Jan Mycielski, Grzegorz Rozenberg et Arto Salomaa (éditeurs), Structures in Logic and Computer Science : A Selection of Essays in Honor of A. Ehrenfeucht, Springer Science & Business Media, coll. « Lecture Notes in Computer Science, Volume 1261 », , 370 p. (ISBN 978-3-540-63246-7, DOI 10.1007/3-540-63246-8).
- Grzegorz Rozenberg et Arto Salomaa (éditeurs), « Formal and Natural Computing: Honoring the 80th Birthday of Andrzej Ehrenfeucht (Special Issue) », Theoretical Computer Science, vol. 457, , p. 1–180 (DOI 10.1016/j.tcs.2012.07.015, lire en ligne).
- Conjecture d'Ehrenfeucht
- Michael H. Albert et John Lawrence, « A proof of Ehrenfeucht's Conjecture », Theoretical Computer Science, vol. 41, , p. 121-123 (DOI 10.1016/0304-3975(85)90066-0, lire en ligne).
Notes et références[modifier | modifier le code]
- Structures in Logic and Computer Science, p. 6.
- (en) « Andrzej Ehrenfeucht », sur le site du Mathematics Genealogy Project.
- En 2008, il est coéditeur d'un volume de souvenirs en l'honneur d'Andrzej Mostowski : Andrzej Mostowski and Foundational Studies.
- Nomination au titre de distinguished professor sur le site de l'université du Colorado.
- Ehrenfeucht 1960/1961.
- Ehrenfeucht et Mycielski 1992, dans la rubrique Unsolved Problems de Richard K. Guy.
- Albert et Lawrence 1985.
- Breaking away from the Mathbook.
- Formal and Natural Computing.
Liens externes[modifier | modifier le code]
- Homepage
- Ressources relatives à la recherche :
