Boris Trakhtenbrot
Boris Avraamovich Trakhtenbrot , also Boaz, Russian Борис Авраамович Трахтенброт , also written Trachtenbrot , (born February 19, 1921 in Tîrnova , Dondușeni district ; † September 19, 2016 ) was a computer scientist from the former Soviet Union and an Israeli mathematician ( Moldova ). He was a professor at Tel Aviv University .
life and work
Trakhtenbrot received his doctorate in 1950 from Pyotr Sergejewitsch Novikow at the Institute for Mathematics of the Ukrainian Academy of Sciences (Decidability Problems for Finite Classes and Definitions of Finite Sets, Russian). In the Soviet Union he worked in Akademgorodok ( Novosibirsk ).
In 1950, he proved the Trakhtenbrot theorem in model theory and logic in his dissertation . It says that the problem of verification in predicate logic is undecidable over the class of finite models.
The sentence by J. Büchi, C. Elgot (1958), and (independently of both) Trakhtenbrot about the equivalence of finite automata and monadic predicate logic 2nd level (MSO) comes from the late 1950s .
Furthermore, in 1964 he proved a fundamental theorem of complexity theory , Borodin's Gap Theorem, which at that time went unnoticed in the West and was rediscovered by Allan Borodin in 1972 and named after him. The sentence roughly says that there are gaps of any size in the hierarchy of complexity classes.
In 2011 Trakhtenbrot received the EATCS Award .
Fonts
- Boris Trachtenbrot Algorithms and Calculators , Berlin, Deutscher Verlag der Wissenschaften 1977
- Trachtenbrot, Nathan Kobrinskij Introduction to the theory of finite automata , Berlin, Akademie Verlag 1967
- Trachtenbrot Why can machines calculate?: An introduction to the logical-mathematical basics of program-controlled calculating machines , Berlin, Deutscher Verlag der Wissenschaften 1962, 1968
- Trakhtenbrot, Ya. M. Barzdin Finite Automata. Behavior and Synthesis , North Holland 1973
Web links
- Dynkin Collection
- Website at Tel Aviv University ( Memento from March 3, 2016 in the Internet Archive )
- Literature by and about Boris Trakhtenbrot in the catalog of the German National Library
Individual evidence
- ↑ Скончался Борис Абрамович Трахтенброт
- ^ Mathematics Genealogy Project
- ↑ Trakthenbrot The impossibility of an algorithm for the decision problem on finite classes (Russian), 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. Logic Grundl. Math., 6, 1960, 66-92, Elgot Decision problems of finite automata design and related arithmetics , Transactions AMS, 98, 1961, 21-51
- ↑ Trakhtenbrot The synthesis of logical networks whose operators can be described by a single-digit predicate logic (Russian), Doklady Akad. Nauka SSSR, 118, 1958, 646-649, Trakhtenbrot Finite automata and single-digit predicate logic , (Russian), Sib. Math. J., 3, 1962, 103-131, English: Finite automata and the logic of one-place predicates , AMS Transl. 59, 1966, 23-55
- ↑ Trakhtenbrot Turing calculations with logarithmic delay (Russian), Algebra and Logic, 3, 1964, 33-48
| personal data | |
|---|---|
| SURNAME | Trakhtenbrot, Boris |
| ALTERNATIVE NAMES | Trakhtenbrot, Boaz; Trachtenbrot, Boris |
| BRIEF DESCRIPTION | Israeli computer scientist |
| DATE OF BIRTH | February 19, 1921 |
| PLACE OF BIRTH | Tîrnova , Dondușeni district |
| DATE OF DEATH | 19th September 2016 |