Avraham Trahtman

Trahtman's solution to the road coloring problem was accepted in 2007 and published in 2009 by the Israel Journal of Mathematics.Avraham N. Trahtman: The Road Coloring Problem. Israel Journal of Mathematics, Vol. 172, 51–60, 2009 The problem arose in the subfield of symbolic dynamics, an abstract part of the field of dynamical systems. The road coloring problem was raised by R. L. Adler and L. W. Goodwyn from the United States, and the Israeli mathematician B. Weiss.R.L. Adler, B. Weiss. Similarity of automorphisms of the torus, Memoirs of the Amer. Math. Soc. 98, Providence, RI, 1970R.L. Adler, L.W. Goodwyn, B. Weiss. Equivalence of topological Markov shifts, Israel Journal of Mathematics 27, 49-63, 1977 The proof used results from earlier work.K. Culik II, J. Karhumaki, J. Kari. A note on synchronized automata and Road Coloring Problem. Developments in Language Theory (5th Int. Conf., Vienna, 2001), Lecture Notes in Computer Science, 2295, 175-185, 2002J. Friedman. On the road coloring problem. Proceedings of the American Mathematical Society 110, 1133-1135, 1990A.N. Trahtman. An Algorithm for Road Coloring. Lect. Notes in Comp. Sci, 7056 (2011), Springer, 349--360

The problem of estimating the length of synchronizing word has a long history and was posed independently by several authors, but it is commonly known as the Černý conjecture. In 1964 Jan Černý conjectured that $(n-1)^2$ is the upper bound for the length of the shortest synchronizing word for any n-state complete DFA (a DFA with complete state transition graph).{{citation |first=Ján |last=Černý |title=Poznámka k homogénnym experimentom s konečnými automatmi |journal=Matematicko-fyzikálny časopis Slovenskej Akadémie Vied |volume=14 |year=1964 |pages=208–216 |url=http://dml.cz/bitstream/handle/10338.dmlcz/126647/MathSlov_14-1964-3_2.pdf}} (in Slovak). English translation: [https://www.jalc.de/issues/2019/issue_24_2-4/jalc-2019-123-132.php A Note on Homogeneous Experiments with Finite Automata]. J. Autom. Lang. Comb. 24(2019), 123-132 If this is true, it would be tight: in his 1964 paper, Černý exhibited a class of automata (indexed by the number n of states) for which the shortest reset words have this length. In 2011 Trahtman published a proofA.N. Trahtman. Modifying the Upper Bound on the Length of Minimal Synchronizing Word. Lect. Notes in Comp. Sci, 6914(2011) Springer, 173-180 of upper bound $n\; (7n^2+6n-16)/48$, but then he found an error in it.{{Cite arXiv |eprint = 1104.2409v6|last1 = Trahtman|first1 = A. N|title = Modifying the upper bound on the length of minimal synchronizing word|class = cs.DM|year = 2011}} The conjecture holds in many partial cases, see for instance, KariJ. Kari. Synchronizing finite automata on Eulerian digraphs. Springer, Lect. Notes in Comp. Sci., 2136, 432-438, 2001. and Trahtman.A.N. Trahtman. The Černý Conjecture for Aperiodic Automata. Discrete Math. Theor. Comput. Sci. v. 9, 2(2007), 3-10

The finite basis problem for semigroups of order less than six in the theory of semigroups was posed by Alfred Tarski in 1966,A. Tarski. Equational logic and equational theories of algebras. Contrib. to math. Logic. Hannover, 1966, (Amst. 1968), 275-288. and repeated by Anatoly Maltsev and L. N. Shevrin. In 1983, Trahtman solved this problem by proving that all semigroups of order less than six are finitely based.A. N. Trahtman. The finite basis question for semigroups of order less than six. Semigroup Forum, 27(1983), 387-389.A.N. Trahtman. Finiteness of a basis of identities of 5-element semigroups. Polugruppy i ih gomomorphismy, Ross. Gos. ped. Univ., Leningrad, 1991, 76-98.

In the theory of varieties of semigroups and universal algebras the problem of existence of covering elements in the lattice of varieties was posed by Evans in 1971.T. Evans. The lattice of semigroup varieties. Semigroup Forum. 2, 1(1971), 1-43. The positive solution of the problem was found by Trahtman.A.N. Trahtman. Covering elements in the lattice of varieties of universal algebras. Mat. Zametky, Moscow, 15(1974), 307-312. He also found a six-element semigroup that generates a variety with a continuum of subvarieties,A.N. Trahtman. A six-element semigroup that generates a variety with a continuum of subvarieties. Ural Gos. Univ. Mat. zap., Alg. syst. i ih mnogoobr., Sverdlovsk, 14(1988), no. 3, 138-143. and varieties of semigroups having no irreducible base of identities.A. N. Trahtman. A variety of semigroups without an irreducible basis of identities. Math. Zametky, Moscow, 21(1977), 865-871.

The theory of locally testable automata can be based on the theory of varieties of locally testable semigroups.A. N. Trahtman. Identities of locally testable semigroups. Comm. Algebra, 27(1999), no. 11, 5405-5412. Trahtman found the precise estimation on the order of local testability of finite automata.A. N. Trahtman. Optimal estimation on the order of local testability of finite automata. Theoret. Comput. Sci., 231(2000), 59-74.

There are results in theoretical mechanicsS.A. Kazak, G.G. Kozhushko, A.N. Trahtman. Calculation of load in discrete chains. Teorija mashin i met. gorn. ob. Sverdlovsk, rel. 1, 1978, 39-51. and in the promising area of extracting moisture from the airB Kogan., A.N. Trahtman. The Moisture from the Air as Water Resource in Arid Region: Hopes, Doubts and Facts. J of Arid Env., London, 2, 53(2003), 231-240. mentioned in "New Scientist".F. Pearce. Pyramids of dew. "New Scientist". 16 April 2005. 52-53.

{{reflist|30em}}

• [http://www.cs.biu.ac.il/~trakht/ Trahtman's page at Bar-Ilan University's Website]
• [http://www.cs.biu.ac.il/~trakht/cv.html Trahtman's Curriculum Vitae]
• [https://arxiv.org/abs/0709.0099 Trahtman's paper (in PDF format)]
• [https://web.archive.org/web/20140306205750/http://www.nbcnews.com/id/23729600/ "63-year-old solves riddle from 1970" on MSNBC]
• [https://www.britannica.com/biography/Avraham-Trahtman "Encyclopedia - Britannica Online Encyclopedia", article: Avraham Trahtman]
• [http://www-history.mcs.st-andrews.ac.uk/ "MacTutor History of Mathematics. Trahtman biography"]
• [https://books.google.com/books?id=WUrVAwAAQBAJ A Mathematical Medley Fifty Easy Pieces on Mathematics] by George G. Szpiro

{{Authority control}}

{{DEFAULTSORT:Trahtman, Avraham}}

Category:1944 births

Category:2024 deaths

Category:Academic staff of Bar-Ilan University

Category:Israeli Jews

Category:21st-century Israeli mathematicians

Category:Russian Jews

Category:20th-century Israeli mathematicians

Category:Ural State University alumni