Boaz (Boris) Trakhtenbrot
Boaz (Boris) Trakhtenbrot
1921-2016
It is 100 years since the birth on 20 February 1921 (Gregorian) of Boaz (Boris) Abramovich Trakhtenbrot, a founding father of computer science and a beloved founding father of our school. Boaz passed away on 19 September 2016 in Rehovot
Boaz was born in Brichevo, a shtetl in Northern Bessarabia (now Moldova), about which he always spoke fondly. He studied at the Moldavian Pedagogical Institute in Kishinev, Chernivtsi National University (Ukraine), Kiev Mathematical Institute (Ukraine), and (unofficially) at Moscow University. After completing his Ph.D. in 1950, under Petr S. Novikov, he took a position at the Belinsky Pedagogical Institute in Penza (Western Russia), and in 1960 joined the just-established Mathematical Institute at Novosibirsk Akademgorodok, where he established and headed the Theory of Automata and Mathematical Linguistics Department. He attained (full) professorship (Doktor nauk) in 1962. He also collaborated with computer designers and helped in the establishment of computer science departments behind the Iron Curtain
On 26 December 1980, Boaz fulfilled his dream and came on aliyah to Israel. He joined our School of Mathematical Sciences, where he was instrumental in the major growth phase of computer science. He remained vitally active for many years after his official retirement in 1991
Boaz is universally admired as a founding father and long-standing pillar of the discipline of computer science. He was the field's pre-eminent distinguished researcher, and a most illustrious trailblazer and disseminator. His contributions span the whole gamut of the theory of computer science. His doctoral dissertation inaugurated finite model theory. He introduced the use of monadic second-order logic as a specification formalism for the infinite behavior of finite automata. He was among the very first to consider time and space efficiency of algorithms (“signalizing functions”) and to speak about abstract complexity measures
He initiated the study of topological aspects of ω-languages and provided a characterization of operators computable by finite automata. His work has led to tools for algorithmic verification now embodied in numerous industrial tools. The list of topics upon which he has made a lasting impression is breathtaking in its scope: decidability problems in logic, finite automata theory, the connection between automata and monadic second-order logic, complexity of algorithms, abstract complexity, algorithmic logic, probabilistic computation, program verification, the lambda calculus and foundations of programming languages, programming semantics, semantics and methodology for concurrency, networks, hybrid systems, and much more. He was unmatched in combining farsighted vision, unfaltering commitment, masterful command of the field, technical virtuoso, esthetic expression, eloquent clarity, and creative vigor with humility and devotion to students and colleagues
( Doctor Honoris Causa - Friedrich Schiller University Jena 1997)
:Three famous theorems in theoretical computer science bear his name
Trakhtenbrot's Theorem (1950): The validity of first-order statements that hold true for all finite universes is undecidable
The Büchi-Elgot-Trakhtenbrot Theorem (1962): Finite automata and weak monadic second-order logic have the same expressive power
The Borodin-Trakhtenbrot Gap Theorem (1964): There are arbitrarily large (computable) gaps in the hierarchy of complexity classes
Boaz was at the same time a master pedagogue and expositor. His book, Algorithms and Automatic Computing Machines, written in Russian in 1957, was translated into English and a dozen other languages, and is recognized worldwide as the first important text in the field. A whole generation of computer scientists was shaped by his textbooks on automata theory. (Indeed, some people studied Russian just to read them.) He played the key role in the dissemination of Soviet computer science research in the West, writing surveys on such topics as Soviet approaches to brute force search (perebor). All told, he published some one hundred articles, books, and monographs
:Appropriately, Boaz received numerous prizes and recognitions for his contributions, including the following
In 1979, Zdzislaw Pawlak, along with Calvin Elgot, Erwin Engeler, Maurice Nivat, and Dana Scott, decided to edit a festschrift “to publish a collection of contributions by outstanding scientists in the field of theoretical computer science and foundations of mathematics in order to honor the 60th anniversary of Professor B. A. Trachtenbrot from Novosibirsk.” However, with the untimely death of Cal Elgot and Boaz’s impending immigration to Israel with his family, the project had to be abandoned
In 1991, our department (viz. Zvi Galil, Amir Pnueli, and Amiram Yehudai, along with Albert Meyer of MIT) organized an International Symposium on Theoretical Computer Science in honor of Boris A. Trakhtenbrot on the occasion of his Retirement and Seventieth Birthday, with the participation of many of the world's foremost computer scientists
In the same year, his colleagues and former students from Latvia published a volume, “Dedicated to Professor B. A. Trakhtenbrot, father of Baltic Computer Science, on the occasion of his 70th birthday” (Springer, 1991)
The Friedrich Schiller University in Jena bestowed on him the degree of doctor honoris causa in 1997
At the Computer Science Logic (CSL) conference in 1998, a special session celebrated “50 years of Trakhtenbrot’s Theorem
In 2001, in honor of his eightieth birthday and his “very important contribution to Formal Languages and Automata,’’ Trakhtenbrot gave the keynote address at a joint plenary session of the International EATCS Colloquium on Automata, Languages and Programming (ICALP) and the ACM Symposium on Theory of Computing (SIGACT)
In 2006, our school held a Computation Day Celebrating Boaz (Boris) Trakhtenbrot's Eighty-Fifth Birthday
In 2008, the volume, Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, appeared in Springer's Festschrift series (Springer, 2008)
In 2011, the European Association for Theoretical Computer Science (EATCS) honored him with their highest honor, the Distinguished Achievements Award
( 1993 Boaz at TAU)
Boaz’s contributions are astounding under any measure; how much more so when consideration is given to the fact that he worked under very adverse conditions: persecution, lack of support, almost no access to foreign meetings, and so on. His undaunted spirit should serve as an inspiration to all
His wisdom, courage, and generosity are sorely missed by all who had the honor and pleasure of his acquaintance
Boaz 100
