Avraham Trahtman - Avraham Trahtman
Avraham Naumovich Trahtman | |
---|---|
narozený | 10. února 1944 Kalinovo, Nevyansky District, Sverdlovská oblast |
Alma mater | Uralská státní univerzita |
Známý jako | řešení problém zbarvení silnice |
Vědecká kariéra | |
Pole | Matematika |
Instituce | Bar-Ilan University |
Doktorský poradce | Lev N. Shevrin |
Avraham Naumovich Trahtman (Trakhtman) (ruština: Абрам Наумович Трахтман; b. 1944, SSSR ) je matematik v Bar-Ilan University (Izrael ). V roce 2007 Trahtman vyřešil problém v kombinatorika která byla otevřena po dobu 37 let, Silniční zbarvení dohad pózovala v roce 1970.[1]
Problém zbarvení silnice byl položen a vyřešen
Trahtmanovo řešení problém zbarvení silnice byl přijat v roce 2007 a zveřejněn v roce 2009 Evropskou komisí Israel Journal of Mathematics.[2] Problém nastal v podpoli symbolická dynamika, abstraktní část oboru dynamické systémy. Problém se zbarvením silnice byl vyvolán uživatelem R. L. Adler a L. W. Goodwyn ze Spojených států a izraelský matematik B. Weiss.[3][4] Použitý důkaz vychází z dřívější práce.[5][6][7]
Černý dohad
Problém odhadu délky synchronizačního slova má dlouhou historii a byl předložen nezávisle několika autory, ale je běžně známý jako Černý dohad. V roce 1964 si to Jan Černý vymyslel je horní mez pro délku nejkratšího synchronizačního slova pro libovolný n-stavový úplný DFA (DFA s grafem přechodu úplného stavu).[8] Pokud je to pravda, bylo by to těsné: ve své práci z roku 1964 Černý vystavil třídu automatů (indexovaných počtem n stavů), pro které mají nejkratší resetovací slova tuto délku. V roce 2011 Trahtman vydal důkaz[9] horní meze , ale pak v něm našel chybu.[10] Domněnka platí v mnoha dílčích případech, viz například Kari[11] a Trahtman.[12]
Jiná práce
Konečný základ problému pro poloskupiny řádu méně než šest v teorii poloskupin představoval Alfred Tarski v roce 1966,[13] a opakováno Anatoly Maltsev a L. N. Shevrin. V roce 1983 Trahtman tento problém vyřešil tím, že dokázal, že všechny poloskupiny řádu menšího než šest jsou definitivně založeny.[14][15]
V teorii odrůdy poloskupin a univerzální algebry - problém existence krycích prvků v mříž odrůd představoval Evans v roce 1971.[16] Pozitivní řešení problému našel Trahtman.[17] Zjistil také, že šestičlenná semigroup, která generuje odrůdu s kontinuem dílčích odrůd,[18] a rozmanitosti poloskupin bez neredukovatelné základny identit.[19]
Teorie místně testovatelné automaty může být založeno na teorii odrůd lokálně testovatelných semigroup.[20] Trahtman našel přesný odhad řádu lokální testovatelnosti konečných automatů.[21]
Výsledky jsou v teoretické mechanice[22] a v slibné oblasti odsávání vlhkosti ze vzduchu[23] uvedeno v „Nový vědec ".[24]
Reference
- ^ J.E. Pin. Na dvou kombinatorických problémech vyplývajících z teorie automatů. Annals of Discrete Math., 17, 535-548, 1983.
- ^ Avraham N. Trahtman: The Road Coloring Problem. Israel Journal of Mathematics, Sv. 172, 51–60, 2009
- ^ R.L. Adler, B. Weiss. Podobnost automorfismů torusu, Memoirs of the Amer. Matematika. Soc. 98, Providence, RI, 1970
- ^ R.L. Adler, L.W. Goodwyn, B. Weiss. Rovnocennost topologických posunů Markov, Izrael J. z Math. 27, 49-63, 1977
- ^ K. Culik II, J. Karhumaki, J. Kari. Poznámka k synchronizovaným automatům a problému zbarvení silnice. Vývoj v teorii jazyků (5th Int. Conf., Vienna, 2001), Lecture Notes in Computer Science, 2295, 175-185, 2002
- ^ J. Friedman. Na silnici zbarvení problém. Proc. Amer. Matematika. Soc. 110, 1133-1135, 1990
- ^ A.N. Trahtman. Algoritmus pro silniční zbarvení. Přednáška Poznámky v komp. Sci, 7056 (2011), Springer, 349-360
- ^ J. Černý, Poznamka k homogenymu eksperimentom s konechnymi automatami, Math.-Fyz. Čas., 14 (1964) 208-215.
- ^ A.N. Trahtman. Úprava horní hranice délky minimálního synchronizačního slova. Přednáška Poznámky v komp. Sci, 6914 (2011) Springer, 173-180
- ^ Trahtman, A. N (2011). Msgstr "Úprava horní meze délky minimálního synchronizačního slova". arXiv:1104.2409v6 [cs.DM ].
- ^ J. Kari. Synchronizace konečných automatů na Eulerianských digrafech. Springer, přednáška. Poznámky v komp. Sci., 2136, 432-438, 2001.
- ^ A.N. Trahtman. Černá domněnka pro aperiodické automaty. Diskrétní matematika. Teor. Comput. Sci. v. 9, 2 (2007), 3-10
- ^ A. Tarski. Rovnicová logika a rovníkové teorie algeber. Přispět. k matematice. Logika. Hannover, 1966, (Amst. 1968), 275-288.
- ^ A. N. Trahtman. Otázka konečného základu pro poloskupiny řádu menší než šest. Semigroup Forum, 27(1983), 387-389.
- ^ A.N. Trahtman. Konečnost základu identit pětičlenných semigroup. Polugruppy i ih gomomorphismy, Ross. Bože. ped. Univ., Leningrad, 1991, 76-98.
- ^ T. Evans. Mříž odrůd poloskupin. Semigroup Forum. 2, 1(1971), 1-43.
- ^ A.N. Trahtman. Krycí prvky v mřížce odrůd univerzálních algeber. Rohož. Zametky, Moskva, 15 (1974), 307 - 312.
- ^ A.N. Trahtman. Šestičlenná poloskupina, která generuje odrůdu s kontinuem subvariet. Ural Gos. Univ. Rohož. zap., Alg. syst. i ih mnogoobr., Sverdlovsk, 14 (1988), č. 1 3, 138-143.
- ^ A. N. Trahtman. Různé poloskupiny bez neredukovatelného základu identit. Matematika. Zametky, Moskva, 21 (1977), 865-871.
- ^ A. N. Trahtman. Identity lokálně testovatelných semigroup. Comm. Algebra, 27 (1999), č. 11, 5405-5412.
- ^ A. N. Trahtman. Optimální odhad v pořadí lokální testovatelnosti konečných automatů. Teoretická. Comput. Sci., 231 (2000), 59-74.
- ^ Kazak, G.G. Kozhushko, A.N. Trahtman. Výpočet zatížení v diskrétních řetězcích. Teorija mashin, kterou jsem potkal. gorn. ob. Sverdlovsk, rel. 1, 1978, 39-51.
- ^ B Kogan., A.N. Trahtman. Vlhkost ze vzduchu jako vodní zdroj v suché oblasti: naděje, pochybnosti a fakta. J of Arid Env., London, 2, 53 (2003), 231-240.
- ^ F. Pearce. Pyramidy rosy. „Nový vědec“. 16. dubna 2005. 52-53.
externí odkazy
- Trahtmanova stránka na webových stránkách Bar-Ilan University
- Trahtman's Curriculum Vitae
- Trahtmanova práce (ve formátu PDF)
- „63letý řeší hádanku z roku 1970“ na MSNBC
- „Encyclopedia - Britannica Online Encyclopedia“, článek: Avraham Trahtman
- „MacTutor History of Mathematics. Trahtman biography“
- Mathematical Medley Fifty Easy Pieces on Mathematics podle George G. Szpiro