Авраам Трахтман - Avraham Trahtman

Авраам Наумович Трахтман
Абрам 008.jpg
Родившийся10 февраля 1944 г.
Калиново, Невьянский район, Свердловская область
Альма-матерУральский государственный университет
Известенрешение проблема окраски дороги
Научная карьера
ПоляМатематика
УчрежденияУниверситет Бар-Илан
ДокторантЛев Николаевич Шеврин

Авраам Наумович Трахтман (Трахтман) (русский: Абрам Наумович Трахтман; б. 1944 г., СССР ) - математик в Университет Бар-Илан (Израиль ). В 2007 году Трахтман решил проблему в комбинаторика который был открыт 37 лет, Гипотеза о раскраске дорог поставлен в 1970 году.[1]

Поставлена ​​и решена проблема окраски дороги

Решение Трахтмана проблема окраски дороги был принят в 2007 г. и опубликован в 2009 г. Израильский математический журнал.[2] Проблема возникла в подполе символическая динамика, абстрактная часть поля динамические системы. Проблема окраски дороги была поднята Р. Л. Адлер и Л. В. Гудвин из США, и израильский математик Б. Вайс.[3][4] В доказательстве использованы результаты более ранней работы.[5][6][7]

Гипотеза Черного

Проблема оценки длины синхронизирующего слова имеет долгую историю и была независимо поставлена ​​несколькими авторами, но обычно она известна как Гипотеза Черного. В 1964 году Ян Черный предположил, что является верхней границей длины кратчайшего синхронизирующего слова для любого полного DFA с n состояниями (DFA с полным графом переходов состояний).[8] Если это так, то это будет сложно: в своей статье 1964 года Черны показал класс автоматов (индексированных числом состояний n), для которых кратчайшие слова сброса имеют эту длину. В 2011 году Трахтман опубликовал доказательство[9] верхней границы , но потом он обнаружил в нем ошибку.[10] Гипотеза верна во многих частных случаях, см., Например, Кари[11] и Трахтман.[12]

Другая работа

Проблема конечного базиса для полугруппы порядка меньше шести в теории полугрупп была поставлена Альфред Тарский в 1966 г.,[13] и повторяется Анатолий Мальцев и Л. Н. Шеврин. В 1983 году Трахтман решил эту проблему, доказав, что все полугруппы порядка меньше шести конечно базируемы.[14][15]

В теории разновидности полугрупп и универсальные алгебры проблема существования покрывающих элементов в решетка разновидностей была предложена Эвансом в 1971 году.[16] Положительное решение проблемы нашел Трахтман.[17] Он также обнаружил шестиэлементную полугруппу, которая порождает многообразие с континуумом подмногообразий,[18] и многообразия полугрупп, не имеющих неприводимой базы тождеств.[19]

Теория локально проверяемый автоматы может быть основана на теории многообразий локально тестируемых полугрупп.[20] Трахтман нашел точную оценку порядка локальной проверяемости конечных автоматов.[21]

Есть результаты по теоретической механике[22] и в перспективной области извлечения влаги из воздуха[23] упомянутый в "Новый ученый ".[24]

Рекомендации

  1. ^ J.E. Pin. О двух комбинаторных задачах теории автоматов. Анналы дискретной математики, 17, 535-548, 1983.
  2. ^ Авраам Н. Трахтман: Проблема раскраски дорог. Израильский математический журнал, Vol. 172, 51–60, 2009 г.
  3. ^ Р.Л. Адлер, Б. Вайс. Подобие автоморфизмов тора, Воспоминания амер. Математика. Soc. 98, Провиденс, Род-Айленд, 1970 г.
  4. ^ Р.Л. Адлер, Л.В. Гудвин, Б. Вайс. Эквивалентность топологических марковских сдвигов, Israel J. of Math. 27, 49-63, 1977 г.
  5. ^ К. Кулик II, Дж. Кархумаки, Дж. Кари. Заметка о синхронизированных автоматах и ​​задаче раскраски дорог. Развитие теории языка (5-я Международная конференция, Вена, 2001 г.), Lecture Notes in Computer Science, 2295, 175-185, 2002
  6. ^ Дж. Фридман. По дороге проблема окраски. Proc. амер. Математика. Soc. 110, 1133–1135, 1990 г.
  7. ^ А.Н. Трахтман. Алгоритм раскраски дорог. Лект. Примечания в комп. Sci, 7056 (2011), Springer, 349--360.
  8. ^ Я. Черны, Познамка к гомогенным экспериментам с конечными автоматами, Math.-Fyz. Čas., 14 (1964) 208--215.
  9. ^ А.Н. Трахтман. Изменение верхней границы длины минимального синхронизирующего слова. Лект. Примечания в комп. Sci, 6914 (2011) Springer, 173-180.
  10. ^ Трахтман, А. Н. (2011). «Изменение верхней границы длины минимального синхронизирующего слова». arXiv:1104.2409v6 [cs.DM ].
  11. ^ J. Kari. Синхронизация конечных автоматов на эйлеровых орграфах. Springer, Lect. Примечания в комп. Sci., 2136, 432-438, 2001.
  12. ^ А.Н. Трахтман. Гипотеза Черни для апериодических автоматов. Дискретная математика. Теор. Comput. Sci. т. 9, 2 (2007), 3-10
  13. ^ А. Тарский. Эквациональная логика и эквациональные теории алгебр. Contrib. к математике. Логика. Ганновер, 1966, (Amst. 1968), 275-288.
  14. ^ А. Н. Трахтман. Вопрос о конечной базисности для полугрупп порядка меньше шести. Полугруппа Форум, 27(1983), 387-389.
  15. ^ А.Н. Трахтман. Конечность базиса тождеств 5-элементных полугрупп. Полугруппы и их гомоморфизм, Росс. Гос. пед. Ун-та, Ленинград, 1991, 76-98.
  16. ^ Т. Эванс. Решетка многообразий полугрупп. Полугруппа Форум. 2, 1(1971), 1-43.
  17. ^ А.Н. Трахтман. Накрывающие элементы в решетке многообразий универсальных алгебр. Мат. Заметки, Москва, 15 (1974), 307-312.
  18. ^ А.Н. Трахтман. Шестиэлементная полугруппа, порождающая многообразие с континуумом подмногообразий. Уральское Гос. Univ. Мат. зап., Алг. syst. и их многообр., Свердловск, 14 (1988), вып. 3, 138-143.
  19. ^ А. Н. Трахтман. Разнообразие полугрупп без неприводимого базиса тождеств. Математика. Заметки, Москва, 21 (1977), 865-871.
  20. ^ А. Н. Трахтман. Тождества локально тестируемых полугрупп. Comm. Алгебра, 27 (1999), вып. 11, 5405-5412.
  21. ^ А. Н. Трахтман. Оптимальная оценка порядка локальной тестируемости конечных автоматов. Теорет. Comput. Sci., 231 (2000), 59-74.
  22. ^ Казак С.А. Кожушко, А. Трахтман. Расчет нагрузки в дискретных цепях. Теория машина, с которой я познакомился. горн. об. Свердловск, отн. 1, 1978, 39-51.
  23. ^ Б Коган., А. Трахтман. Влага из воздуха как водный ресурс в засушливом регионе: надежды, сомнения и факты. J. of Arid Env., Лондон, 2, 53 (2003), 231-240.
  24. ^ Ф. Пирс. Пирамиды росы. «Новый ученый». 16 апреля 2005 г. 52–53.

внешняя ссылка