Boris Trakhtenbrot

Boris Avraamovich Trakhtenbrot, auch Boʿaz, auch Trachtenbrot (russisch Борис Авраамович Трахтенброт, hebräisch בּוֹרִיס [בּוֹעז] טְרַכְטֶנְבּרוֹט Boris [Boʿaz] Trachtenbrot; * 19. Februar 1921 in Tîrnova, Rajon Dondușeni; † 19. September 2016) war ein aus der ehemaligen Sowjetunion (Moldawien) stammender israelischer Informatiker und mathematischer Logiker. Er war Professor an der Universität Tel Aviv.

Leben und Werk

Trakhtenbrot wurde 1950 bei Pjotr Sergejewitsch Nowikow am Institut für Mathematik der Ukrainischen Akademie der Wissenschaften promoviert (Entscheidbarkeitsprobleme für endliche Klassen und Definitionen endlicher Mengen, Russisch). In der Sowjetunion wirkte er in Akademgorodok (Nowosibirsk). Ende 1980 wanderte er nach Israel aus. Anfang 1981 wurde er Professor an der Universität Tel Aviv.

1950 bewies er in seiner Dissertation den Satz von Trakhtenbrot in der Modelltheorie und Logik. Er besagt, dass das Problem der Verifizierung in der Prädikatenlogik über der Klasse endlicher Modelle unentscheidbar ist.

Aus dem Ende der 1950er Jahre stammt der Satz von J. Büchi, C. Elgot (1958), und (unabhängig von beiden) Trakhtenbrot über die Äquivalenz von endlichen Automaten und monadischer Prädikatenlogik 2. Stufe (MSO).

Des Weiteren bewies er 1964 einen grundlegenden Satz der Komplexitätstheorie, den Lückensatz von Borodin (Gap Theorem), der aber damals im Westen unbeachtet blieb und 1972 von Allan Borodin neu gefunden und nach ihm benannt wurde. Der Satz besagt in etwa, dass es beliebig große Lücken in der Hierarchie der Komplexitätsklassen gibt.

2011 erhielt Trakhtenbrot den EATCS-Award.

Schriften

Boris Trachtenbrot Algorithmen und Rechenautomaten, Berlin, Deutscher Verlag der Wissenschaften 1977
Trachtenbrot, Nathan Kobrinskij Einführung in die Theorie endlicher Automaten, Berlin, Akademie Verlag 1967
Trachtenbrot Wieso können Automaten rechnen ?: eine Einführung in die logisch-mathematischen Grundlagen programmgesteuerter Rechenautomaten, Berlin, Deutscher Verlag der Wissenschaften 1962, 1968
Trakhtenbrot, Ya. M. Barzdin Finite Automata. Behavior and Synthesis, North Holland 1973

Weblinks

Commons: Boris Trakhtenbrot – Sammlung von Bildern, Videos und Audiodateien

John J. O’Connor, Edmund F. Robertson: Boris Avraamovich Trakhtenbrot. In: MacTutor History of Mathematics archive (englisch).
Dynkin Collection
Webseite an der Universität Tel Aviv (Memento vom 3. März 2016 im Internet Archive)
Literatur von und über Boris Trakhtenbrot im Katalog der Deutschen Nationalbibliothek

Einzelnachweise

↑ Скончался Борис Абрамович Трахтенброт
↑ Boris (Boaz) Abramovich Trakhtenbrot im Mathematics Genealogy Project (englisch) abgerufen am 24. Juli 2025.
↑ Trakthenbrot Die Unmöglichkeit eines Algorithmus für das Entscheidungsproblem auf endlichen Klassen (russisch), Doklady Akad. Nauka SSSR, 70, 1950, 569-572
↑ Büchi, Elgot Decision problems of weak second order arithmetics and finite automata, Notices AMS, 5, 1958, 834, Büchi Weak second order arithmetic and finite automata, Z. Math. Logik Grundl. Math., 6, 1960, 66-92, Elgot Decision problems of finite automata design and related arithmetics, Transactions AMS, 98, 1961, 21-51
↑ Trakhtenbrot Die Synthese logischer Netze deren Operatoren durch eine einstellige Prädikatenlogik beschrieben werden können (russisch), Doklady Akad. Nauka SSSR, 118, 1958, 646-649, Trakhtenbrot Endliche Automaten und einstellige Prädikatenlogik, (russisch), Sib. Math. J., 3, 1962, 103-131, englisch: Finite automata and the logic of one-place predicates, AMS Transl. 59, 1966, 23-55
↑ Trakhtenbrot Turing Berechnungen mit logarithmischer Verzögerung (russisch), Algebra und Logik, 3, 1964, 33-48

Personendaten
NAME	Trakhtenbrot, Boris
ALTERNATIVNAMEN	Trakhtenbrot, Boaz; Trachtenbrot, Boris
KURZBESCHREIBUNG	israelischer Informatiker
GEBURTSDATUM	19. Februar 1921
GEBURTSORT	Tîrnova, Rajon Dondușeni
STERBEDATUM	19. September 2016

[1] Скончался Борис Абрамович Трахтенброт

[2] Boris (Boaz) Abramovich Trakhtenbrot im Mathematics Genealogy Project (englisch) abgerufen am 24. Juli 2025.

[3] Trakthenbrot Die Unmöglichkeit eines Algorithmus für das Entscheidungsproblem auf endlichen Klassen (russisch), Doklady Akad. Nauka SSSR, 70, 1950, 569-572

[4] Büchi, Elgot Decision problems of weak second order arithmetics and finite automata, Notices AMS, 5, 1958, 834, Büchi Weak second order arithmetic and finite automata, Z. Math. Logik Grundl. Math., 6, 1960, 66-92, Elgot Decision problems of finite automata design and related arithmetics, Transactions AMS, 98, 1961, 21-51

[5] Trakhtenbrot Die Synthese logischer Netze deren Operatoren durch eine einstellige Prädikatenlogik beschrieben werden können (russisch), Doklady Akad. Nauka SSSR, 118, 1958, 646-649, Trakhtenbrot Endliche Automaten und einstellige Prädikatenlogik, (russisch), Sib. Math. J., 3, 1962, 103-131, englisch: Finite automata and the logic of one-place predicates, AMS Transl. 59, 1966, 23-55

[6] Trakhtenbrot Turing Berechnungen mit logarithmischer Verzögerung (russisch), Algebra und Logik, 3, 1964, 33-48