# Andrzej Ehrenfeucht

Andrzej Ehrenfeucht (né le 8 août 1932 à 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

Ehrenfeucht étudie les mathématiques à l'université de Varsovie et soutient en 1961 une thèse sous la direction d'Andrzej Mostowski à l'institut de mathématiques de l'Académie polonaise des sciences$^,$. 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é$^,$.
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.
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.
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. 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.
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

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, le deuxième à l'occasion de son 80e anniversaire.

## Publications

* 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,‎ 1992, p. 373.
* Patricia Baggett et Andrzej Ehrenfeucht, Breaking Away from the Math Book : Creative Projects for Grades K-6, Rowman & Littlefield Education, 1995, 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, 1999, 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, 2003, 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, 2008, 447 p. (ISBN 978-1-58603-782-6, lire en ligne)