Avraham Naumovich Trahtman (Trakhtman) (russian: Абрам Наумович Трахтман; b. 1944,
USSR
The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, it was nominally a federal union of fifteen nationa ...
) is a mathematician at
Bar-Ilan University
Bar-Ilan University (BIU, he, אוניברסיטת בר-אילן, ''Universitat Bar-Ilan'') is a public research university in the Tel Aviv District city of Ramat Gan, Israel. Established in 1955, Bar Ilan is Israel's second-largest academic i ...
(
Israel
Israel (; he, יִשְׂרָאֵל, ; ar, إِسْرَائِيل, ), officially the State of Israel ( he, מְדִינַת יִשְׂרָאֵל, label=none, translit=Medīnat Yīsrāʾēl; ), is a country in Western Asia. It is situated ...
). In 2007, Trahtman solved a problem in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
that had been open for 37 years, the
Road Coloring Conjecture In graph theory the road coloring theorem, known previously as the road coloring conjecture, deals with Synchronization, synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destinati ...
posed in 1970.
Road coloring problem posed and solved
Trahtman's solution to the
road coloring problem In graph theory the road coloring theorem, known previously 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 any othe ...
was accepted in 2007 and published in 2009 by the ''
Israel Journal of Mathematics
'' Israel Journal of Mathematics'' is a peer-reviewed mathematics journal published by the Hebrew University of Jerusalem (Magnes Press).
Founded in 1963, as a continuation of the ''Bulletin of the Research Council of Israel'' (Section F), the jou ...
''. The problem arose in the subfield of
symbolic dynamics In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics (e ...
, an abstract part of the field of
dynamical systems
In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in an ambient space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a p ...
. 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 computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state.Avraham Trakhtma ...
. In 1964 Jan Černý conjectured that
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).
[ (in Slovak). English translation]
A Note on Homogeneous Experiments with Finite Automata
J. Autom. Lang. Comb. 24(2019), 123-132 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
, 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
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
of order less than six in the theory of semigroups was posed by
Alfred Tarski
Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
in 1966, and repeated by
Anatoly Maltsev Anatoly Ivanovich Maltsev (also: Malcev, Mal'cev; Russian: Анато́лий Ива́нович Ма́льцев; 27 November N.S./14 November O.S. 1909, Moscow Governorate – 7 June 1967, Novosibirsk) was born in Misheronsky, near Moscow, and ...
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
Variety may refer to:
Arts and entertainment Entertainment formats
* Variety (radio)
* Variety show, in theater and television
Films
* ''Variety'' (1925 film), a German silent film directed by Ewald Andre Dupont
* ''Variety'' (1935 film), ...
of semigroups and
universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular groups as the object of study, ...
s the problem of existence of covering elements in the
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an ornam ...
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
An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...
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
''New Scientist'' is a magazine covering all aspects of science and technology. Based in London, it publishes weekly English-language editions in the United Kingdom, the United States and Australia. An editorially separate organisation publishe ...
''".
[F. Pearce. Pyramids of dew. "New Scientist". 16 April 2005. 52-53.]
References
External links
Trahtman's page at Bar-Ilan University's WebsiteTrahtman's paper (in PDF format)"63-year-old solves riddle from 1970" on MSNBC"Encyclopedia - Britannica Online Encyclopedia", article: Avraham Trahtman"MacTutor History of Mathematics. Trahtman biography"''A Mathematical Medley Fifty Easy Pieces on Mathematics''by
George G. Szpiro
{{DEFAULTSORT:Trahtman, Avraham
Academic staff of Bar-Ilan University
1944 births
Living people
Israeli Jews
21st-century Israeli mathematicians
Russian Jews
20th-century Israeli mathematicians
Ural State University alumni