Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
18 апреля 2016 г., г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Zoom
 


Об автоматных группах и их обобщениях

А. Л. Таламбуца

Количество просмотров:
Эта страница:211

Аннотация: В начале 1990-х годов в связи с необходимостью эффективно проводить вычисления в бесконечных группах, Кэннон и Тёрстон создали теорию автоматных групп.
Группа называется автоматной, если выполнены два следующих условия. Во-первых для элементов группы есть некоторая форма записи в порождающих, которая называется нормальной формой и распознаётся конечным автоматом. Во-вторых, для каждой порождающей $b$ существует конечный автомат, проверяющий для любых двух нормальных форм $X$ и $Y$, выполнено ли равенство $X=Yb$.
Класс автоматных групп достаточно широкий - в него входят все конечные группы, все гиперболические группы, группы отражений Кокстера, группы кос и другие. Основным свойством автоматных групп является то, что проблема равенства в этом классе решается за квадратичное время.
В докладе будет рассказано об автоматных группах и их свойствах, а также об обобщении Мясникова, Харлампович и Хусаинова, которые предложили не ограничивать язык нормальных форм языком порождающих группы. Оказывается, что это эквивалентно требованию того, что у графа Кэли группы есть автоматная структура. Такое обобщение позволяет существенно расширить класс автоматных групп, сохраняя при этом многие полезные свойства этого класса.
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024