Boris Avraamovich Trakhtenbrot (en russe Борис Авраамович Трахтенброт, en hébreu בועז טרכטנברוט), dont le prénom est aussi Boaz, (né le 19 février 1921 à Tîrnova (raion de Dondușeni)) est un informaticien théoricien, logicien et mathématicien israélien originaire de Bessarabie en Moldavie, dans l'anciennne URSS. Il est professeur à l'université de Tel Aviv.

Éléments biographiques

Trakhtenbrot soutient en 1950 une thèse (« Decidability Problems for Finite Classes and Definitions of Finite Sets ») sous la direction de Pyotr Sergeyevich Novikov (en) à l'Institut de mathématiques de l'Académie ukrainienne des sciences. En Union soviétique, il travaille d'abord à Penza, à environ 700 km au sud-est de Moscou, puis à partir du début des années 1960 et jusqu'à la fin des années 1970, au département de cybernétique de l'institut de mathématiques de Akademgorodok (Novossibirsk). Trakhtenbrot émigre en Israël fin 1980. Il est professeur à l'université de Tel Aviv jusqu'en 1991, où il prend sa retraite.

Œuvre

Plusieurs de ses travaux en font un des pères fondateurs de l'informatique théorique. Il est décrit comme un grand visionnaire, pionnier dans plusieurs directions, et introduisant des concepts novateurs qui ont eu un impact considérable rétrospectivement, mais qui n'ont pas trouvé l'écho qu'ils méritaient à l'époque. Ces travaux, alors classés dans la catégorie « cybernétique », rencontraient en URSS des critiques et des réticences, à la fois scientifiques et politiques.

En 1964, Trakhtenbrot démontre un théorème fondamental en théorie de la complexité, appelé maintenant le théorème de la lacune de Borodin (en anglais « gap theorem », « théorème de la lacune » chez Périfel). Il n'a pas été remarqué en Occident à l'époque, et a été redécouvert en 1972 par Allan Borodin; il porte maintenant le nom du second. Le théorème dit qu'il existe des trous arbitrairement grands dans la hiérarchie des classes de complexité.

Dans sa thèse, en 1950, il démontre ce qui est le théorème de Trakhtenbrot de la théorie des modèles. Il dit que le problème de la vérification dans le calcul des prédicats de la classe des modèles finis est indécidable ou, de manière équivalente, que l'ensemble des formules du premier ordre qui sont valides dans des structures finies n'est pas récursivement énumérable.

À la fin des années 1950, Trakhtenbrot d'une part, J. Büchi et C. Elgot d'autre part, démontrent de manière indépendante l'équivalence entre les automates finis et la logique monadique du second ordre (MSO), résultat appelé le théorème de Büchi-Elgot-Trakhtenbrot.

À la fin des années 1970, Trakhtenbrot travaille sur divers concepts de concurrence. Il fait également des contributions en théorie des automates finis, complexité abstrait, logique algorithmique, calcul probabiliste, vérification de programmes, lambda calcul, sémantique de programmation, théorie des types, sémantique des systèmes hybrides ou concurrents.

Parmi ses élèves, il y a Janis M. Barzdins, Rusins V. Freivalds, Valery Nepomnyashchy, Vladimir Yu. Sazanov, A. Ja. Dikovsky, Miroslav I. Kratko, Nikolai Beljakin.

Prix et distinctions

En 2011, il reçoit le Prix EATCS. Il est docteur honoris causa de l'université d'Iéna.

Publications (sélection)

Ses livres ont été traduits en de nombreuses langues, notamment en allemand et en anglais.

• Boris A. Trakhtenbrot, Algorithms_And_Automatic_Computing_Machines, Boston, Massachucetts, D.C. Heath and Company, 1963, 101 p. (lire en ligne)
• N. E. Kobrinskii et Boris A. Trakhtenbrot, Introduction to the theory of finite automata, Amsterdam, North-Holland, 1965, x+337 p. (Math Reviews 0186454)
• Boris A. Trakhtenbrot et Ya. M. Barzdin, Finite Automata. Behavior and Synthesis, Amsterdam-London et New York,, North Holland et American Elsevier Publishing, coll. « Fundamental Studies in Computer Science, Vol. 1. », 1973, xi+321 p. (Math Reviews 0351686)

• I. Yaglom, Boris A. Trakhtenbrot, E. Ventsel et A. Solodovnikov, Nouvelles orientations des mathématiques, Moscou, Édition Mir, coll. « Initiation aux Mathématiques », 1975, 408 p. (Math Reviews 0449951) — La deuxième partie contient une version du texte de 1963.