Авраам Трахтман
Авраам Наумович Трахтман | |
|---|---|
 | |
| Рожденный | 10 февраля 1944 г. |
| Умер | 17 июля 2024 г. (80 лет) |
| Альма-матер | Уральский государственный университет |
| Известный | решение проблемы с раскраской дороги |
| Научная карьера | |
| Поля | Математика |
| Учреждения | Университет Бар-Илан |
| Докторантура | Лев Николаевич Шеврин |
Авраам Наумович Трахтман (Трахтман) ( русский : Абрам Наумович Трахтман ; 10 февраля 1944 — 17 июля 2024) — израильский математик советского происхождения, академик Университета Бар-Илан ( Израиль ). В 2007 году Тратман решил задачу комбинаторики , которая была открыта в течение 37 лет, — гипотезу о раскраске дорог , сформулированную в 1970 году. [1] Трахтман умер в Иерусалиме 17 июля 2024 года в возрасте 80 лет. [2]
Проблема окраски дорог поставлена и решена
[ редактировать ]Решение Трахтмана проблемы окраски дорог было принято в 2007 году и опубликовано в 2009 году в Израильском математическом журнале . [3] Проблема возникла в области символической динамики , абстрактной части области динамических систем . Задача о раскраске дорог была поставлена Р.Л. Адлером и Л.В. Гудвином из США, а также израильским математиком Б. Вайсом . [4] [5] В доказательстве использованы результаты более ранних работ. [6] [7] [8]
Черная гипотеза
[ редактировать ]Проблема оценки длины синхронизирующего слова имеет долгую историю и была поставлена независимо несколькими авторами, но широко известна как гипотеза Черного . В 1964 году Ян Черны предположил, что является верхней границей длины кратчайшего синхронизирующего слова для любого полного DFA с n состояниями (DFA с полным графом переходов состояний). [9] Если это правда, то это было бы сложно: в своей статье 1964 года Черны представил класс автоматов (индексированных по числу состояний n), для которых самые короткие слова сброса имеют такую длину. В 2011 году Трахтман опубликовал доказательство. [10] верхней границы , но потом нашел в нем ошибку. [11] Гипотеза верна во многих частных случаях, см., например, Kari [12] и Трахтман. [13]
Другая работа
[ редактировать ]Проблема конечного базиса для полугрупп порядка меньше шести в теории полугрупп была поставлена Альфредом Тарским в 1966 году: [14] и повторено Анатолием Мальцевым и Л. Н. Шевриным. В 1983 году Трахтман решил эту проблему, доказав, что все полугруппы порядка меньше шести конечно базируемы. [15] [16]
В теории многообразий полугрупп и универсальных алгебр проблема существования накрывающих элементов в решетке многообразий была поставлена Эвансом в 1971 г. [17] Положительное решение проблемы было найдено Трахтманом. [18] Он также нашел полугруппу из шести элементов, которая порождает многообразие с континуумом подмногообразий. [19] и многообразия полугрупп, не имеющие неприводимой базы тождеств. [20]
Теория локально проверяемых автоматов может быть основана на теории многообразий локально проверяемых полугрупп. [21] Трахтман нашел точную оценку порядка локальной тестируемости конечных автоматов. [22]
Есть результаты по теоретической механике [23] и в перспективной области извлечения влаги из воздуха [24] упоминается в журнале « New Scientist ». [25]
Ссылки
[ редактировать ]- ^ JE Пин. О двух комбинаторных задачах, возникающих из теории автоматов. Анналы дискретной математики, 17, 535–548, 1983.
- ^ «Авраам Трахтман 1944 – 2024» . Навсегда пропущенный . Проверено 5 августа 2024 г.
- ^ Авраам Н. Трахтман: Проблема раскраски дорог. Израильский математический журнал , Vol. 172, 51–60, 2009 г.
- ^ Р.Л. Адлер, Б. Вайс. Подобие автоморфизмов тора, Мемуары амер. Математика. Соц. 98, Провиденс, Род-Айленд, 1970 г.
- ^ Р.Л. Адлер, Л.В. Гудвин, Б. Вайс. Эквивалентность топологических марковских сдвигов, Израильский математический журнал 27, 49–63, 1977 г.
- ^ К. Чулик II, Дж. Карумаки, Дж. Кари. Замечание о синхронизированных автоматах и задаче раскраски дорог. Развитие теории языка (5-я Международная конференция, Вена, 2001 г.), Конспекты лекций по информатике, 2295, 175–185, 2002 г.
- ^ Дж. Фридман. Проблема с окраской на дороге. Труды Американского математического общества 110, 1133–1135, 1990 г.
- ^ А.Н. Трахтман. Алгоритм раскраски дорог. Лект. Примечания в Комп. Sci, 7056 (2011), Спрингер, 349–360.
- ^ Черны, Ян (1964), «Заметки об однородных экспериментах с конечными автоматами» (PDF) , Математико-физический журнал Словацкой академии наук , 14 : 208–216 (на словацком языке). Английский перевод: Заметки об однородных экспериментах с конечными автоматами . Дж. Автомат. Ланг. Гребень. 24(2019), 123-132
- ^ А.Н. Трахтман. Изменение верхней границы длины минимального синхронизирующего слова. Лект. Примечания в Комп. Sci, 6914 (2011) Спрингер, 173–180.
- ^ Трахтман, А.Н. (2011). «Изменение верхней границы длины минимального синхронизирующего слова». arXiv : 1104.2409v6 [ cs.DM ].
- ^ Дж. Кари. Синхронизация конечных автоматов на эйлеровых орграфах. Спрингер, лект. Примечания в Комп. Sci., 2136, 432-438, 2001.
- ^ А.Н. Трахтман. Гипотеза Черного для апериодических автоматов. Дискретная математика. Теор. Вычислить. наук. т. 9, 2(2007), 3-10
- ^ А. Тарский. Эквациональная логика и эквациональные теории алгебр. Вклад. к математике. Логика. Ганновер, 1966, (Амст. 1968), 275–288.
- ^ А.Н. Трахтман. Вопрос о конечной базисе полугрупп порядка меньше шести. Форум полугруппы , 27 (1983), 387-389.
- ^ А.Н. Трахтман. Конечность базиса тождеств 5-элементных полугрупп. Полугруппы и их гомоморфизмы, Росс. Гос. пед. ун-та, Ленинград, 1991, 76-98.
- ^ Т. Эванс. Решетка многообразий полугрупп. Полугрупповой форум . 2, 1 (1971), 1-43.
- ^ А.Н. Трахтман. Накрывающие элементы в решетке многообразий универсальных алгебр. Мат. Заметки, Москва, 15(1974), 307-312.
- ^ А.Н. Трахтман. Полугруппа из шести элементов, порождающая многообразие с континуумом подмногообразий. Урал Гос. унив. Мат. зап., Алг. система и их многообр., Свердловск, 14(1988), вып. 3, 138–143.
- ^ А.Н. Трахтман. Разновидность полугрупп без неприводимого базиса тождеств. Математика. Заметки, Москва, 21(1977), 865-871.
- ^ А.Н. Трахтман. Тождества локально проверяемых полугрупп. Комм. Алгебра, 27 (1999), вып. 11, 5405-5412.
- ^ А.Н. Трахтман. Оптимальная оценка порядка локальной тестируемости конечных автоматов. Теория. Вычислить. Sci., 231(2000), 59-74.
- ^ С.А. Казак, Г.Г. Кожушко, А.Н. Трахтман. Расчет нагрузки в дискретных цепях. Машина Теория, которую я встретил. горн. об. Свердловск, отн. 1, 1978, 39–51.
- ^ Б. Коган., А. Н. Трахтман. Влага воздуха как водный ресурс в засушливом регионе: надежды, сомнения и факты. Журнал Arid Env., Лондон, 2, 53 (2003), 231–240.
- ^ Ф. Пирс. Пирамиды росы. «Новый учёный». 16 апреля 2005 г. 52–53.
Внешние ссылки
[ редактировать ]- Страница Трахтмана на сайте Университета Бар-Илан
- Биографическая справка Трахтмана
- Статья Тратмана (в формате PDF)
- «63-летний мужчина разгадывает загадку 1970 года» на MSNBC
- «Энциклопедия - Интернет-энциклопедия Britannica», статья: Авраам Трахтман
- «MacTutor История математики. Биография Тратмана»
- Математическое попурри «Пятьдесят простых пьес по математике», Джордж Г. Шпиро
