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

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