Введение

В математике автоматическая группа — это конечно порожденная группа, снабженная несколькими конечными автоматами с состояниями. Эти автоматы представляют собой граф Кэли группы. То есть, они могут определить, находится ли данное словесное представление элемента группы в "канонической форме", и могут определить, отличаются ли два элемента, заданные в канонических словах, на генератор. Более точно, пусть G — группа, а A — конечное множество порождающих элементов. Тогда автоматическая структура G относительно A представляет собой набор конечных автоматов с состояниями:
приемник слов, который для каждого элемента G принимает хотя бы одно слово, представляющее его;
множители, по одному для каждого , которые принимают пару (w1, w2), где w1 и w2 — слова, принятые приемником слов, тогда и только тогда, когда в G.

Свойство автоматичности не зависит от выбора порождающего множества.

Свойства

Автоматические группы имеют словесную проблему, разрешимую за квадратичное время. Более точно, заданное слово может быть фактически приведено к канонической форме за квадратичное время, на основе чего словесная проблема может быть решена путем проверки, представляют ли канонические формы двух слов один и тот же элемент (с использованием мультипликатора для). Автоматические группы характеризуются свойством "сопровождающих путешественников". Пусть обозначает расстояние между в графе Кейли. Тогда G является автоматической группой относительно акцептора слов L тогда и только тогда, когда существует константа такая, что для всех слов, различающихся не более чем одним образующим, расстояние между соответствующими префиксами u и v ограничено C. Иными словами, где для k-го префикса (или самого если ). Это означает, что при синхронном чтении слов можно отслеживать разницу между обоими элементами с помощью конечного числа состояний (окрестность единицы с диаметром C в графе Кейли).