Andrzej Ehrenfeucht

mathématicien et informaticien américain

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.

Andrzej Ehrenfeucht
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Voir et modifier les données sur Wikidata (92 ans)
VilniusVoir et modifier les données sur Wikidata
Nationalités
Formation
Université de Varsovie
Lycée Nicolas-Copernic de Łódź (d)Voir et modifier les données sur Wikidata
Activités
Autres informations
A travaillé pour
Membre de
Directeur de thèse
Site web

Biographie scientifique

modifier

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

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
  • 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
Volumes d'hommages
Conjecture d'Ehrenfeucht

Notes et références

modifier
  1. a b et c Structures in Logic and Computer Science, p. 6.
  2. (en) « Andrzej Ehrenfeucht », sur le site du Mathematics Genealogy Project.
  3. En 2008, il est coéditeur d'un volume de souvenirs en l'honneur d'Andrzej Mostowski : Andrzej Mostowski and Foundational Studies.
  4. Nomination au titre de distinguished professor sur le site de l'université du Colorado.
  5. Ehrenfeucht 1960/1961.
  6. Ehrenfeucht et Mycielski 1992, dans la rubrique Unsolved Problems de Richard K. Guy.
  7. Albert et Lawrence 1985.
  8. Breaking away from the Mathbook.
  9. Formal and Natural Computing.

Liens externes

modifier