Boris Trakhtenbrot

Boris Trakhtenbrot
Trakhtenbrot, à gauche, avec Gerd Wechsung et Jörg Rothe
Biographie
Naissance
Voir et modifier les données sur Wikidata
Briceva (d) (royaume de Roumanie)Voir et modifier les données sur Wikidata
Décès
Voir et modifier les données sur Wikidata (à 95 ans)
Rehovot (Israël)Voir et modifier les données sur Wikidata
Sépulture
RehovotVoir et modifier les données sur Wikidata
Nom dans la langue maternelle
Борис Авраамович Трахтенброт ou בועז טרכטנברוטVoir et modifier les données sur Wikidata
Nationalité
roumain, puis soviétique, enfin israélien
Formation
Université pédagogique d'État « Ion Creanga » (en) (-)
Université nationale de Tchernivtsi (-)
Institut de mathématiques de l'Académie nationale des sciences d'Ukraine (en) (-)Voir et modifier les données sur Wikidata
Activités
Mathématicien, informaticienVoir et modifier les données sur Wikidata
Autres informations
A travaillé pour
Université de Tel Aviv (-)
Institut de mathématiques de Sobolev (en) (-)
Université d'État de Novossibirsk (-)
Penza Pedagogical Institute named after V. G. Belinsky (d) (-)Voir et modifier les données sur Wikidata
Directeur de thèse
Piotr NovikovVoir et modifier les données sur Wikidata
Distinction
Prix EATCS ()Voir et modifier les données sur Wikidata
Œuvres principales
Théorème de Trakhtenbrot, gap theorem (d), Büchi-Elgot-Trakhtenbrot theorem (d)Voir et modifier les données sur Wikidata

modifier - modifier le code - modifier WikidataDocumentation du modèle

Boris Avraamovitch Trakhtenbrot (en russe : Борис Авраамович Трахтенброт, en hébreu : בועז טרכטנברוט), dont le prénom est aussi Boaz, né le [1],[2] dans le village de Briceva (raion de Dondușeni, en Moldavie, alors intégré au royaume de Roumanie), et mort le à Rehovot (Israël), est un informaticien théoricien, logicien et mathématicien roumain, soviétique, devenu israélien.

Il termine sa carrière comme professeur à l'université de Tel Aviv.

Biographie

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.

Œ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[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.

Prix et distinctions

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

Livres (sélection)

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, , 101 p. (lire en ligne)
  • (en) N. E. Kobrinskii et Boris A. Trakhtenbrot, Introduction to the Theory of Finite Automata, Amsterdam, North-Holland, , 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. », , 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 », , 408 p. (MR 0449951) — La deuxième partie contient une version du texte de 1963.

Notes et références

  • (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).
  1. ↑ a b c et d Arnon Avron, Nachum Dershowitz et Alexander Rabinovich (éditeurs), Pillars of Computer Science : Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, Springer-Verlag, coll. « Lecture Notes in Computer Science Vol. 4800 », , xxi+683 (ISBN 978-3-540-78126-4, DOI 10.1007/978-3-540-78127-1).
  2. ↑ Lawrence M. Fisher, « In Memoriam : Boris Trakhtenbrot », ACM NEWS, Communications of the ACM, (consulté le ).
  3. ↑ (en) « Boris A. Trakhtenbrot », sur le site du Mathematics Genealogy Project
  4. ↑ a b et c Paul G. Spirakis, « Laudatio Boris (Boaz) Trakhtenbrot », EATCS Awards, European Association for Theoretical Computer Science, .
  5. ↑ (ru) Boris A. Trakhtenbrot, « Turing Computations with Logarithmic Delay », Algebra i Logika, vol. 3, no 4,‎ , p. 33-48.
  6. ↑ Sylvain Perifel, Complexité algorithmique, Paris, Ellipses Marketing, coll. « Références sciences », , 432 p. (ISBN 978-2-7298-8692-9, lire en ligne), p. 34
  7. ↑ (ru) Boris A. Trakhtenbrot, « Impossibility of an algorithm for the decision problem on finite classes », Doklady Akademii Nauk SSSR, vol. 70,‎ , p. 569-572
  8. ↑ (ru) Boris A. Trakhtenbrot, « The synthesis of logical nets whose operators are described in terms of one-place predicate calculus », Doklady Akad. Nauka SSSR, vol. 118,‎ , p. 646-649.
  9. ↑ (ru) Boris A. Trakhtenbrot, « Finite automata and the logic of one-place predicates », Sib. Math. J., vol. 3,‎ , p. 103-131 — Traduction anglaise : AMS Transl., vol. 59, 1966, p. 23-55.
  10. ↑ (en) J. Büchi et C. Elgot, « Decision problems of weak second order arithmetics and finite automata », Notices AMS, vol. 5,‎ , p. 834.
  11. ↑ (en) J. Büchi, « Weak second order arithmetic and finite automata », Z. Math. Logik Grundl. Math., vol. 6,‎ , p. 66-92.
  12. ↑ (en) C. Elgot, « Decision problems of finite automata design and related arithmetics », Transactions AMS, vol. 98,‎ , p. 21-51.

Liens externes

  • Notices d'autoritéVoir et modifier les données sur Wikidata :
    • 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 rechercheVoir et modifier les données sur Wikidata :
    • Digital Bibliography & Library Project
    • 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, (consulté le ).
v · m
Lauréats du prix EATCS
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail de la logique
  • icône décorative Portail des mathématiques
  • icône décorative Portail d’Israël