Boris Trakhtenbrot

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[3]. 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[1]. Il est professeur à l'université de Tel Aviv jusqu'en 1991, où il prend sa retraite.

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[4]. Ces travaux, alors classés dans la catégorie « cybernétique », rencontraient en URSS des critiques et des réticences[1], à la fois scientifiques et politiques.

En 1964[5], 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 (de) (en anglais « gap theorem », « théorème de la lacune » chez Perifel[6]). 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[7]. 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[8] - [9], J. Büchi et C. Elgot d'autre part[10] - [11] - [12], 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[4].

À 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, on compte[1] Janis M. Barzdins, Rusins V. Freivalds, Valery Nepomnyashchy, Vladimir Yu. Sazanov, A. Ja. Dikovsky, Miroslav I. Kratko, Nikolai Beljakin.

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

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

• (en) Boris A. Trakhtenbrot, Algorithms And Automatic Computing Machines, Boston, Massachucetts, D.C. Heath and Company, 1963, 101 p. (lire en ligne)
• (en) N. E. Kobrinskii et Boris A. Trakhtenbrot, Introduction to the Theory of Finite Automata, Amsterdam, North-Holland, 1965, x+337 (MR 0186454)
• (en) Boris A. Trakhtenbrot et Ya. M. Barzdin, Finite Automata. Behavior and Synthesis, Amsterdam-Londres et New York,, North Holland et American Elsevier Publishing, coll. « Fundamental Studies in Computer Science, Vol. 1. », 1973, xi+321 (MR 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. (MR 0449951) — La deuxième partie contient une version du texte de 1963.

• (de)/(en) Cet article est partiellement ou en totalité issu des articles intitulés en allemand « Boris Trakhtenbrot » (voir la liste des auteurs) et en anglais « Boris Trakhtenbrot » (voir la liste des auteurs).

• Notices d'autorité :

  • VIAF
  • ISNI
  • BnF (données)
  • IdRef
  • LCCN
  • GND
  • Pays-Bas
  • Pologne
  • Israël
  • NUKAT
  • Catalogne
  • Suède
  • Australie
  • Norvège
  • Tchéquie
  • WorldCat
• Page personnelle, université de Tel Aviv.
• (en) Interview de Boris A. Trakhtenbrot, 18 octobre 1981, Dynkin Collection.
• Ressources relatives à la recherche :
  • (en) Digital Bibliography & Library Project
  • (en) Mathematics Genealogy Project
• (ru) Трахтенброт. Livres de Trakhtenbrot sur le site Alib.ru.
• Lawrence M. Fisher, « In Memoriam : Boris Trakhtenbrot », ACM NEWS, Communications of the ACM, 21 septembre 2016 (consulté le 18 octobre 2016).