Avraham Trahtman

Avraham Naumovich Trakhtman (also Trahtman ), ( born February 10, 1944 in Kalinowo, Sverdlovsk Oblast ) is a Soviet- Israeli mathematician.

Trahtman studied at the State University of the Urals in Sverdlovsk with the conclusion of 1967. Afterwards, he was at the Technical University of the Urals, where he became a teacher and taught until 1984. In 1973 he received his doctorate at Lew Schewrin at the State University of the Urals. Because he was Jewish, his career in the Soviet Union was hampered in the 1970s. In the late 1980s he was also active in the Russian democratic movement. In 1991 he became an assistant professor at the Pedagogical University in Sverdlovsk, but left in 1992, the Soviet Union and went to Israel. First, he had to there on occasional work before 1995, he got a job at Bar- Ilan University.

In 1974 he solved a problem of T. Evans ( 1971) on associations of semigroup varieties.

In 1983, he solved the problem of finite basis for semigroups of Alfred Tarski ( 1966).

In 2007, he solved the road coloring problem ( Road coloring problem) by Roy Adler, LW Goodwyn and Benjamin Weiss ( 1970 ). The problem asks for the existence of a synchronized coloring of the edges in certain directed graphs (one from each node carry the same number of edges out which are all colored differently ). Coloration allows a schedule indicated ( as a sequence of colors in a word W ) to come from any node of the graph P to another node Q of the graph, where W P is equal for all. The problem has its origin in the theory of automata.

He also made progress in another open problem of the theory of finite automata, the problem Cerny (1964 Jan Cerny ), an upper limit of the length of the shortest synchronizing words.