Boris Trakhtenbrot

Boris Avraamovich Trakhtenbrot, auch Boaz, russisch Борис Авраамович Трахтенброт, auch Trachtenbrot geschrieben, (* 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.

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).

Er bewies 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 wurde, nach dem er benannt wurde. Der Satz besagt in etwa, das es beliebig große Lücken in der Hierarchie der Komplexitätsklassen gibt.

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).

2011 erhielt er den EATCS-Award.