Edit filter log

'{{Infobox scientist |name = Avraham Naumovich Trahtman |image = Abram 008.jpg | |image_size = 250px |caption = |birth_date = 10 February 1944 |birth_place = Kalinovo, [[Nevyansky District]], [[Sverdlovsk Oblast]] |death_date = |death_place = |residence = [[Jerusalem]], [[Israel]] |nationality = |ethnicity = |field = [[Mathematics]] |work_institutions = [[Bar-Ilan University]] |alma_mater = [[Ural State University]] |doctoral_advisor = [[Lev N. Shevrin]] |doctoral_students = |known_for = solving the [[road coloring problem]] |prizes = }} '''Avraham Naumovich Trahtman''' (Trakhtman) ({{lang-ru|Абрам Наумович Трахтман}}; b. 1944, [[USSR]]) is a mathematician at [[Bar-Ilan University]] ([[Israel]]). In 2007, Trahtman solved a problem in [[combinatorics]] that had been open for 37 years, the [[Road Coloring Conjecture]] posed in 1970.<ref>J.E. Pin. On two combinatorial problems arising from automata theory. Annals of Discrete Math., 17, 535-548, 1983.</ref> ==Road coloring problem posed and solved== Trahtman's solution to the [[road coloring problem]] was accepted in 2007 and published in 2009 by the ''[[Israel Journal of Mathematics]]''.<ref>Avraham N. Trahtman: The Road Coloring Problem. ''[[Israel Journal of Mathematics]]'', Vol. 172, 51&ndash;60, 2009</ref> 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 [[Roy Adler|R. L. Adler]] and L. W. Goodwyn from the United States, and the Israeli mathematician B. Weiss.<ref>R.L. Adler, B. Weiss. Similarity of automorphisms of the torus, Memoirs of the Amer. Math. Soc. 98, Providence, RI, 1970</ref><ref>R.L. Adler, L.W. Goodwyn, B. Weiss. Equivalence of topological Markov shifts, Israel J. of Math. 27, 49-63, 1977</ref> The proof used results from earlier work.<ref>K. Culik II, J. Karhumaki, J. Kari. A note on synchronized automata and Road Coloring Problem. [[International Conference on Developments in Language Theory|Developments in Language Theory]] (5th Int. Conf., Vienna, 2001), Lecture Notes in Computer Science, 2295, 175-185, 2002</ref><ref>J. Friedman. On the road coloring problem. Proc. of the Amer. Math. Soc. 110, 1133-1135, 1990</ref><ref>A.N. Trahtman. An Algorithm for Road Coloring. Lect. Notes in Comp. Sci, 7056 (2011), Springer, 349--360</ref> ==Cerny conjecture== 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)² 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).<ref>J. Černý, Poznamka k homogenym eksperimentom s konechnymi automatami, Math.-Fyz. Čas., 14(1964) 208--215. </ref> 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 Trakhtman published a proof<ref>A.N. Trahtman. Modifying the Upper Bound on the Length of Minimal Synchronizing Word. Lect. Notes in Comp. Sci, 6914(2011) Springer, 173-180</ref> of upper bound n(7n²+6n-16)/48, but the proof was later found to be erroneous.<ref>http://arxiv.org/abs/1104.2409v6</ref> The conjecture holds in many partial cases, see for instance, Kari<ref>J. Kari. Synchronizing finite automata on Eulerian digraphs. Springer, Lect. Notes in Comp. Sci., 2136, 432-438, 2001.</ref> and Trahtman.<ref>A.N. Trahtman. The Černý Conjecture for Aperiodic Automata. Discr. Math. & Theor. Comput. Sci. v. 9, 2(2007), 3-10</ref> ==Other work== The finite basis problem for [[semigroups]] of order less than six in the theory of semigroups was posed by [[Alfred Tarski]] in 1966,<ref>A. Tarski. Equational logic and equational theories of algebras. Contrib. to math. Logic. Hannover, 1966, (Amst. 1968), 275-288.</ref> 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.<ref>A. N. Trahtman. The finite basis question for semigroups of order less than six. Semigroup Forum, 27(1983), 387-389.</ref><ref>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.</ref> In the theory of [[Variety (universal algebra)|varieties]] of semigroups and [[universal algebra]]s the problem of existence of covering elements in the [[lattice (order)|lattice]] of varieties was posed by Evans in 1971.<ref>T. Evans. The lattice of semigroup varieties. Semigroup Forum. 2, 1(1971), 1-43.</ref> The positive solution of the problem was found by Trahtman.<ref>A.N. Trahtman. Covering elements in the lattice of varieties of universal algebras. Mat. Zametky, Moscow, 15(1974), 307-312.</ref> He also found a six-element semigroup that generates a variety with a continuum of subvarieties,<ref>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.</ref> and varieties of semigroups having no irreducible base of identities.<ref>A. N. Trahtman. A variety of semigroups without an irreducible basis of identities. Math. Zametky, Moscow, 21(1977), 865-871.</ref> The theory of [[locally testable]] [[automata theory|automata]] can be based on the theory of varieties of locally testable semigroups.<ref>A. N. Trahtman. Identities of locally testable semigroups. Comm. Algebra, 27(1999), no. 11, 5405-5412.</ref> Trahtman found the precise estimation on the order of local testability of finite automata.<ref>A. N. Trahtman. Optimal estimation on the order of local testability of finite automata. Theoret. Comput. Sci., 231(2000), 59-74.</ref> There are results in theoretical mechanics<ref>S.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.</ref> and in the promising area of extracting moisture from the air<ref>B 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.</ref> mentioned in "''[[New Scientist]]''".<ref>F. Pearce. Pyramids of dew. "New Scientist". 16 April 2005. 52-53.</ref> ==References== {{reflist|30em}} ==External links== *{{MathGenealogy |id=59507 }} *[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] *[http://arxiv.org/pdf/0709.0099v4 Trahtman's paper (in PDF format)] *[http://www.msnbc.msn.com/id/23729600/ "63-year-old solves riddle from 1970" on MSNBC] *[http://www.britannica.com "Encyclopedia - Britannica Online Encyclopedia", article: Avraham Trahtman] *[http://www-history.mcs.st-andrews.ac.uk/ "MacTutor History of Mathematics. Trahtman biography"] *[http://www.uprack.com/israeli-mathematicians-adi-shamir-giulio-racah-sahron-shelah-zlil-sela=robert-aumann-michael-0-rabin-oded-schramm-avraham-trahtman "Israeli Mathematicians, Adi Shamir, Giulio Racah, Saharon Shelah, Zlil Sela, Robert Aumann, Michael O. Rabin, Oded Schramm, Avraham Trahtman, Llc Books, 2010"] *[http://books.google.com/books/ "A Mathematical Medley Fifty Easy Pieces on Mathematics. George G. Szpiro"] {{Persondata <!-- Metadata: see [[Wikipedia:Persondata]]. --> | NAME = Trahtman, Avraham | ALTERNATIVE NAMES = | SHORT DESCRIPTION = Israeli mathematicians | DATE OF BIRTH = 1944 | PLACE OF BIRTH = [[USSR]] | DATE OF DEATH = | PLACE OF DEATH = }} {{DEFAULTSORT:Trahtman, Avraham}} [[Category:1944 births]] [[Category:Living people]] [[Category:Israeli academics]] [[Category:Israeli Jews]] [[Category:Israeli mathematicians]] [[Category:Russian Jews]] [[Category:21st-century mathematicians]] [[Category:Mathematics and culture]]'