Avraham Trahtman

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 the road 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 at Bar-Ilan University (Israel). In 2007, Trahtman solved a problem in combinatorics that had been open for 37 years, the Road 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 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 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 by Alfred Tarski [ A. Tarski. Equational logic and equational theories of algebras. Contrib. to math. Logic. Hannover, 1966, (Amst. 1968), 275-288.] in 1966 and repeated immediately by Anatoly Maltsev and Shevrin. The problem was solved by Trahtman 17 years later in 1983 [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 algebras 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.] in 1971. 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.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Trahtman, Avraham — ▪ 2009 Avraham Trakhtman  born Feb. 10, 1944, Kalinovo, Sverdlovsk oblast, U.S.S.R. [now in Russia]   The astonishing news emerged in 2008 that in September 2007 a 63 year old Israeli mathematician, Avraham Trahtman, had solved a long standing… …   Universalium

  • Synchronizing word — This drawing represents a DFA with eight states and two input symbols, red and blue. The word blue red red blue red red blue red red is a synchronizing word that sends all states to the yellow state; the word blue blue red blue blue red blue blue …   Wikipedia

  • Трахтман, Абрам Наумович — В Википедии есть статьи о других людях с такой фамилией, см. Трахтман. Абрам Наумович Трахтман Дата рождения …   Википедия

  • Road coloring problem — In graph theory the road coloring theorem, known until recently as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from… …   Wikipedia

  • Unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Millennium Prize Problems Of the seven Millennium Prize Problems set by the Clay Mathematics Institute, the six ones yet to be solved are:… …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • List of mathematicians (T) — NOTOC Tac * Tachard, Guy (France, 1651 1712) * Tacquet, André (Belgium, 1612 1660) * Taguchi, Genichi (Japan, 1924 ) * Tahan, Malba (Brazil, 1895 1974) * Tahta, Dikran (Britain, 1928 2006) * Taimina, Daina (Latvia, ? ) * Tait, Peter Guthrie… …   Wikipedia

  • Синхронизируемое слово — «»В компьютерной науке, точнее, в теории детерминированных конечных автоматов (ДКА), синхронизирующее слово (или сжимающая последовательность) во входном алфавите автомата отображает все его состояния в одно и то же состояние[1]. То есть, если… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”