Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Авраам Наумович Трахтман
Абрам 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], упомянутой в « New Scientist ». [24]

Ссылки [ править ]

  1. ^ JE Pin. О двух комбинаторных задачах теории автоматов. Анналы дискретной математики, 17, 535-548, 1983.
  2. ^ Авраам Н. Трахтман: Проблема окраски дороги. Израильский математический журнал , Vol. 172, 51–60, 2009 г.
  3. ^ RL Адлер, Б. Вайс. Подобие автоморфизмов тора, Воспоминания амер. Математика. Soc. 98, Провиденс, Род-Айленд, 1970 г.
  4. ^ RL Адлер, LW Гудвин, Б. Вайс. Эквивалентность топологических марковских сдвигов, Israel J. of Math. 27, 49-63, 1977 г.
  5. ^ К. Кулик II, Дж. Кархумаки, Дж. Кари. Заметка о синхронизированных автоматах и ​​задаче раскраски дорог. Развитие теории языка (5-я Международная конференция, Вена, 2001 г.), Лекционные заметки по компьютерным наукам, 2295, 175-185, 2002
  6. ^ Дж. Фридман. По дороге проблема окраски. Proc. амер. Математика. Soc. 110, 1133–1135, 1990 г.
  7. ^ А. Н. Трахтман. Алгоритм раскраски дорог. Лект. Примечания в комп. Sci, 7056 (2011), Springer, 349--360.
  8. ^ J. Черны, Poznamka к homogenym eksperimentom с konechnymi automatami, Math.-Fyz. Čas., 14 (1964) 208--215.
  9. ^ А. Н. Трахтман. Изменение верхней границы длины минимального синхронизирующего слова. Лект. Примечания в комп. Sci, 6914 (2011) Springer, 173-180.
  10. ^ Трахтман, А. Н. (2011). «Изменение верхней границы длины минимального синхронизирующего слова». arXiv : 1104.2409v6 [ cs.DM ].
  11. ^ Дж. Кари. Синхронизация конечных автоматов на эйлеровых орграфах. 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.

Внешние ссылки [ править ]

  • Страница Трахтмана на сайте Университета Бар-Илан
  • Биографические данные Трахтмана
  • Статья Трахтмана (в формате PDF)
  • "63-летний мужчина разгадывает загадку 1970 года" на MSNBC
  • "Энциклопедия - Британская онлайн-энциклопедия", статья: Авраам Трахтман
  • "История математики MacTutor. Биография Трахтмана"
  • Математическая смесь «Пятьдесят легких пьес по математике » Джорджа Спиро