fbpx
Wikipedia

Avraham Trahtman

October 19, 2023

Avraham Naumovich Trahtman (Trakhtman) (Russian: Абрам Наумович Трахтман; b. 1944, USSR) 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 posed in 1970.[1]

Avraham Naumovich Trahtman
Born10 February 1944
Kalinovo, Nevyansky District, Sverdlovsk Oblast
Alma materUral State University
Known forsolving the road coloring problem
Scientific career
FieldsMathematics
InstitutionsBar-Ilan University
Doctoral advisorLev N. Shevrin

Road coloring problem posed and solved Edit

Trahtman's solution to the road coloring problem was accepted in 2007 and published in 2009 by the Israel Journal of Mathematics.[2] 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.[3][4] The proof used results from earlier work.[5][6][7]

Černý conjecture Edit

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   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).[8] 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[9] of upper bound  , but then he found an error in it.[10] The conjecture holds in many partial cases, see for instance, Kari[11] and Trahtman.[12]

Other work Edit

The finite basis problem for semigroups of order less than six in the theory of semigroups was posed by Alfred Tarski in 1966,[13] 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.[14][15]

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

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

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

References Edit

  1. ^ J. E. Pin. On two combinatorial problems arising from automata theory. Annals of Discrete Math., 17, 535-548, 1983.
  2. ^ Avraham N. Trahtman: The Road Coloring Problem. Israel Journal of Mathematics, Vol. 172, 51–60, 2009
  3. ^ R.L. Adler, B. Weiss. Similarity of automorphisms of the torus, Memoirs of the Amer. Math. Soc. 98, Providence, RI, 1970
  4. ^ R.L. Adler, L.W. Goodwyn, B. Weiss. Equivalence of topological Markov shifts, Israel Journal of Mathematics 27, 49-63, 1977
  5. ^ 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
  6. ^ J. Friedman. On the road coloring problem. Proceedings of the American Mathematical Society 110, 1133-1135, 1990
  7. ^ A.N. Trahtman. An Algorithm for Road Coloring. Lect. Notes in Comp. Sci, 7056 (2011), Springer, 349--360
  8. ^ Černý, Ján (1964), "Poznámka k homogénnym experimentom s konečnými automatmi" (PDF), Matematicko-fyzikálny časopis Slovenskej Akadémie Vied, 14: 208–216 (in Slovak). English translation: A Note on Homogeneous Experiments with Finite Automata. J. Autom. Lang. Comb. 24(2019), 123-132
  9. ^ A.N. Trahtman. Modifying the Upper Bound on the Length of Minimal Synchronizing Word. Lect. Notes in Comp. Sci, 6914(2011) Springer, 173-180
  10. ^ Trahtman, A. N (2011). "Modifying the upper bound on the length of minimal synchronizing word". arXiv:1104.2409v6 [cs.DM].
  11. ^ J. Kari. Synchronizing finite automata on Eulerian digraphs. Springer, Lect. Notes in Comp. Sci., 2136, 432-438, 2001.
  12. ^ A.N. Trahtman. The Černý Conjecture for Aperiodic Automata. Discrete Math. Theor. Comput. Sci. v. 9, 2(2007), 3-10
  13. ^ A. Tarski. Equational logic and equational theories of algebras. Contrib. to math. Logic. Hannover, 1966, (Amst. 1968), 275-288.
  14. ^ A. N. Trahtman. The finite basis question for semigroups of order less than six. Semigroup Forum, 27(1983), 387-389.
  15. ^ 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.
  16. ^ T. Evans. The lattice of semigroup varieties. Semigroup Forum. 2, 1(1971), 1-43.
  17. ^ A.N. Trahtman. Covering elements in the lattice of varieties of universal algebras. Mat. Zametky, Moscow, 15(1974), 307-312.
  18. ^ A.N. Trahtman. A six-element 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.
  19. ^ A. N. Trahtman. A variety of semigroups without an irreducible basis of identities. Math. Zametky, Moscow, 21(1977), 865-871.
  20. ^ A. N. Trahtman. Identities of locally testable semigroups. Comm. Algebra, 27(1999), no. 11, 5405-5412.
  21. ^ A. N. Trahtman. Optimal estimation on the order of local testability of finite automata. Theoret. Comput. Sci., 231(2000), 59-74.
  22. ^ 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.
  23. ^ 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.
  24. ^ F. Pearce. Pyramids of dew. "New Scientist". 16 April 2005. 52-53.

External links Edit

  • Trahtman's page at Bar-Ilan University's Website
  • Trahtman's Curriculum Vitae
  • Trahtman'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

October 19, 2023
avraham, trahtman, avraham, naumovich, trahtman, trakhtman, russian, Абрам, Наумович, Трахтман, 1944, ussr, mathematician, ilan, university, israel, 2007, trahtman, solved, problem, combinatorics, that, been, open, years, road, coloring, conjecture, posed, 197. Avraham Naumovich Trahtman Trakhtman Russian Abram Naumovich Trahtman b 1944 USSR 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 posed in 1970 1 Avraham Naumovich TrahtmanBorn10 February 1944Kalinovo Nevyansky District Sverdlovsk OblastAlma materUral State UniversityKnown forsolving the road coloring problemScientific careerFieldsMathematicsInstitutionsBar Ilan UniversityDoctoral advisorLev N Shevrin Contents 1 Road coloring problem posed and solved 2 Cerny conjecture 3 Other work 4 References 5 External linksRoad coloring problem posed and solved EditTrahtman s solution to the road coloring problem was accepted in 2007 and published in 2009 by the Israel Journal of Mathematics 2 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 3 4 The proof used results from earlier work 5 6 7 Cerny conjecture EditThe 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 Cerny conjecture In 1964 Jan Cerny conjectured that n 1 2 displaystyle n 1 2 nbsp 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 8 If this is true it would be tight in his 1964 paper Cerny 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 9 of upper bound n 7 n 2 6 n 16 48 displaystyle n 7n 2 6n 16 48 nbsp but then he found an error in it 10 The conjecture holds in many partial cases see for instance Kari 11 and Trahtman 12 Other work EditThe finite basis problem for semigroups of order less than six in the theory of semigroups was posed by Alfred Tarski in 1966 13 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 14 15 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 16 The positive solution of the problem was found by Trahtman 17 He also found a six element semigroup that generates a variety with a continuum of subvarieties 18 and varieties of semigroups having no irreducible base of identities 19 The theory of locally testable automata can be based on the theory of varieties of locally testable semigroups 20 Trahtman found the precise estimation on the order of local testability of finite automata 21 There are results in theoretical mechanics 22 and in the promising area of extracting moisture from the air 23 mentioned in New Scientist 24 References Edit J E Pin On two combinatorial problems arising from automata theory Annals of Discrete Math 17 535 548 1983 Avraham N Trahtman The Road Coloring Problem Israel Journal of Mathematics Vol 172 51 60 2009 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 Journal of Mathematics 27 49 63 1977 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 Proceedings of the American Mathematical Society 110 1133 1135 1990 A N Trahtman An Algorithm for Road Coloring Lect Notes in Comp Sci 7056 2011 Springer 349 360 Cerny Jan 1964 Poznamka k homogennym experimentom s konecnymi automatmi PDF Matematicko fyzikalny casopis Slovenskej Akademie Vied 14 208 216 in Slovak English translation A Note on Homogeneous Experiments with Finite Automata J Autom Lang Comb 24 2019 123 132 A N Trahtman Modifying the Upper Bound on the Length of Minimal Synchronizing Word Lect Notes in Comp Sci 6914 2011 Springer 173 180 Trahtman A N 2011 Modifying the upper bound on the length of minimal synchronizing word arXiv 1104 2409v6 cs DM J Kari Synchronizing finite automata on Eulerian digraphs Springer Lect Notes in Comp Sci 2136 432 438 2001 A N Trahtman The Cerny Conjecture for Aperiodic Automata Discrete Math Theor Comput Sci v 9 2 2007 3 10 A Tarski Equational logic and equational theories of algebras Contrib to math Logic Hannover 1966 Amst 1968 275 288 A N Trahtman The finite basis question for semigroups of order less than six Semigroup Forum 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 T Evans The lattice of semigroup varieties Semigroup Forum 2 1 1971 1 43 A N Trahtman Covering elements in the lattice of varieties of universal algebras Mat Zametky Moscow 15 1974 307 312 A N Trahtman A six element 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 A N Trahtman A variety of semigroups without an irreducible basis of identities Math Zametky Moscow 21 1977 865 871 A N Trahtman Identities of locally testable semigroups Comm Algebra 27 1999 no 11 5405 5412 A N Trahtman Optimal estimation on the order of local testability of finite automata Theoret Comput Sci 231 2000 59 74 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 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 F Pearce Pyramids of dew New Scientist 16 April 2005 52 53 External links EditTrahtman s page at Bar Ilan University s Website Trahtman s Curriculum Vitae Trahtman 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 Retrieved from https en wikipedia org w index php title Avraham Trahtman amp oldid 1138229735, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.