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

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





Для просмотра файлов Вам могут потребоваться








Семинар отдела математической логики «Теория доказательств»
18 апреля 2016 г., г. Москва, МИАН, ауд. 530
 


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

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

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

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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018