|
|
Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
18 апреля 2016 г., г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Zoom
|
|
|
|
|
|
Об автоматных группах и их обобщениях
А. Л. Таламбуца |
Количество просмотров: |
Эта страница: | 211 |
|
Аннотация:
В начале 1990-х годов в связи с необходимостью эффективно проводить вычисления в бесконечных группах, Кэннон и Тёрстон создали теорию автоматных групп.
Группа называется автоматной, если выполнены два следующих условия. Во-первых для элементов группы есть некоторая форма записи в порождающих, которая называется нормальной формой и распознаётся конечным автоматом. Во-вторых, для каждой порождающей $b$ существует конечный автомат, проверяющий для любых двух нормальных форм $X$ и $Y$, выполнено ли равенство $X=Yb$.
Класс автоматных групп достаточно широкий - в него входят все конечные группы, все гиперболические группы, группы отражений Кокстера, группы кос и другие. Основным свойством автоматных групп является то, что проблема равенства в этом классе решается за квадратичное время.
В докладе будет рассказано об автоматных группах и их свойствах, а также об обобщении Мясникова, Харлампович и Хусаинова, которые предложили не ограничивать язык нормальных форм языком порождающих группы. Оказывается, что это эквивалентно требованию того, что у графа Кэли группы есть автоматная структура. Такое обобщение позволяет существенно расширить класс автоматных групп, сохраняя при этом многие полезные свойства этого класса.
|
|