Avraham Trahtman

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. 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. The proof used results from earlier work.

Černý 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 ) 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). 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 proof of upper bound n ( 7 n 2 + 6 n − 16 ) / 48 , but then he found an error in it. The conjecture holds in many partial cases, see for instance, Kari and Trahtman.

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, 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.

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. The positive solution of the problem was found by Trahtman. He also found a six-element semigroup that generates a variety with a continuum of subvarieties, and varieties of semigroups having no irreducible base of identities.

The theory of locally testable automata can be based on the theory of varieties of locally testable semigroups. Trahtman found the precise estimation on the order of local testability of finite automata.

There are results in theoretical mechanics and in the promising area of extracting moisture from the air mentioned in "New Scientist".