- Avraham Trahtman
Infobox Scientist
name = Avraham Trahtman
box_width =
|
image_width =
caption =
birth_date =
birth_place =
death_date =
death_place =
residence =Jerusalem ,Israel
citizenship =
nationality =
ethnicity =
field =Mathematics
work_institutions =Bar-Ilan University
alma_mater =
doctoral_advisor =
doctoral_students =
known_for = solving theroad coloring problem
author_abbrev_bot =
author_abbrev_zoo =
influences =
influenced =
prizes =
religion =
footnotes =Avraham Trahtman (Trakhtman) (b.
1944 , Ph.D. (1973 ) and former degree (1967 ) at Ural University,Sverdlovsk ) is a mathematician atBar-Ilan University (Israel ). In2007 , Trahtman solved a problem incombinatorics that had been open for 37 years, theRoad Coloring Conjecture [J.E. Pin. On two combinatorial problems arising from automata theory. Annals of Discrete Math., 17, 535-548, 1983.] posed in 1970.Road coloring problem posed and solved
Trahtman's
road coloring problem solution was accepted and published in 2007 by the "Israel Journal of Mathematics ". The problem arose in the subfield ofsymbolic dynamics , an abstract part of the field ofdynamical systems . The road coloring problem was raised by R. L. Adler and L. W. Goodwyn from the United States and Israeli mathematician B. Weiss [R.L. Adler, B. Weiss. Similarity of automorphisms of the torus, Memoirs of the Amer. Math. Soc. 98, Providence, RI, 1970.] [R.L. Adler, L.W. Goodwyn, B. Weiss. Equivalence of topological Markov shifts, Israel J. of Math. 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, 2002.] [J. Friedman. On the road coloring problem. Proc. of the Amer. Math. Soc. 110, 1133-1135, 1990.] [J. Kari. Synchronizing finite automata on Eulerian digraphs. Springer, Lect. Notes in Comp. Sci., 2136, 432-438, 2001.] .Other work
The problem of the finite basis question for
semigroups of order less than six in the theory of semigroups was posed byAlfred Tarski [ A. Tarski. Equational logic and equational theories of algebras. Contrib. to math. Logic. Hannover, 1966, (Amst. 1968), 275-288.] in1966 and repeated immediately byAnatoly Maltsev and Shevrin. The problem was solved by Trahtman 17 years later in1983 [A. N. Trahtman. The finite basis question for semigroups of order less than six. Semigroup Forum, NY, 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 algebra s the problem of existence of covering elements in the lattice of varieties was posed by Evans [T. Evans. The lattice of semigroup varieties. Semigroup Forum. 2, 1(1971), 1-43.] in1971 . The positive solution of the problem was found by Trakhtman [ 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 sixelement 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 mechanics [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.] and in the promising area of extracting moisture from the air [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.] mentioned in "
New Scientist " [F. Pearce. Pyramids of dew. "New Scientist". 16 April 2005. 52-53.] .External links
* [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]References
*Jerusalem Post 9-2-2008 Health and Sci Tech
Wikimedia Foundation. 2010.