Автоматическая группа

В математике автоматическая группа — это конечно порожденная группа, оснащенная несколькими автоматами с конечным числом состояний . Эти автоматы представляют собой граф Кэли группы. То есть они могут определить, находится ли данное словесное представление элемента группы в «канонической форме», и могут определить, отличаются ли два элемента, заданные в канонических словах, генератором. ^[1]

Точнее, пусть G — группа, а A — конечное множество образующих. Тогда автоматическая структура группы G относительно A представляет собой набор конечных автоматов: ^[2]

, акцептор слова который принимает для каждого элемента G хотя бы одно слово из $A^{\ast }$ представляющий его;
множители , по одному на каждый $a\in A\cup \{1\}$ , которые принимают пару ( w ₁ , w ₂ ) для слов w _i, принимаемых акцептором слова, именно тогда, когда $w_{1}a=w_{2}$ в Г.

Свойство автоматизма не зависит от набора образующих. ^[3]

Характеристики

В автоматических группах есть словесная задача , решаемая за квадратичное время. Более строго, данное слово действительно может быть приведено в каноническую форму за квадратичное время, на основе чего проблема слов может быть решена путем проверки того, представляют ли канонические формы двух слов один и тот же элемент (используя множитель для $a=1$ ). ^[4]

Автоматические группы характеризуются свойством попутчика . ^[5] Позволять $d(x,y)$ обозначают расстояние между $x,y\in G$ в графе Кэли $G$ . Тогда группа G автоматична по отношению к акцептору слова L тогда и только тогда, когда существует константа $C\in \mathbb {N}$ такой, что для всех слов $u,v\in L$ которые отличаются не более чем на один генератор, расстояние между соответствующими префиксами u и v ограничено C . Другими словами, $\forall u,v\in L,d(u,v)\leq 1\Rightarrow \forall k\in \mathbb {N} ,d(u_{|k},v_{|k})\leq C$ где $w_{|k}$ для k-го префикса $w$ (или $w$ сам, если $k>|w|$ ). Это означает, что при синхронном чтении слов можно отслеживать разницу между обоими элементами с конечным числом состояний (окрестность единицы с диаметром C в графе Кэли).

Примеры автоматических групп

К автоматическим группам относятся:

Конечные группы . Чтобы убедиться в этом, рассмотрим регулярный язык как набор всех слов конечной группы.
Евклидовы группы
Все конечно порожденные группы Кокстера ^[6]
Геометрически конечные группы

Примеры неавтоматических групп

Группы Баумслага – Солитара
Неевклидовы группы нильпотентные

Биавтоматические группы

Группа называется биавтоматической , если она имеет два автомата-перемножителя для левого и правого умножения на элементы порождающего множества соответственно. Биавтоматическая группа явно автоматична. ^[7]

Примеры включают в себя:

Гиперболические группы . ^[8]
Любая группа Артина конечного типа , включая группы кос . ^[8]

Автоматические конструкции

Идея описания алгебраических структур с помощью конечных автоматов может быть обобщена с групп на другие структуры. ^[9] Например, оно естественным образом обобщается на автоматические полугруппы . ^[10]

Ссылки

^ Эпштейн, Дэвид Б.А .; Кэннон, Джеймс В .; Холт, Дерек Ф.; Леви, Сильвио В.Ф.; Патерсон, Майкл С .; Терстон, Уильям П. (1992), Текстовая обработка в группах , Бостон, Массачусетс: Jones and Bartlett Publishers, ISBN 0-86720-244-0 .
^ Эпштейн и др. (1992) , Раздел 2.3, «Автоматические группы: Определение», стр. 45–51.
^ Эпштейн и др. (1992) , раздел 2.4, «Инвариантность при замене генераторов», стр. 52–55.
^ Эпштейн и др. (1992) , Теорема 2.3.10, с. 50.
^ Кэмпбелл, Колин М.; Робертсон, Эдмунд Ф.; Рускуц, Ник; Томас, Ричард М. (2001), «Автоматические полугруппы» (PDF) , Theoretical Computer Science , 250 (1–2): 365–391, doi : 10.1016/S0304-3975(99)00151-6
^ Бринк и Хоулетт (1993), «Свойство конечности и автоматическая структура групп Кокстера», Mathematische Annalen , 296 , Springer Berlin/Heidelberg: 179–190, doi : 10.1007/bf01445101 , ISSN 0025-5831 , S2CID 122177473 .
^ Бирже, Жан-Камиль (2000), Алгоритмические проблемы в группах и полугруппах , Тенденции в математике, Биркхойзер, с. 82, ISBN 0-8176-4130-0
^ Jump up to: ^а ^б Чарни, Рут (1992), «Группы Артина конечного типа биавтоматичны», Mathematische Annalen , 292 : 671–683, doi : 10.1007/BF01444642 , S2CID 120654588
^ Хусаинов, Бахадыр; Рубин, Саша (2002), Некоторые мысли об автоматических структурах , CiteSeerX 10.1.1.7.3913
^ Эпштейн и др. (1992) , Раздел 6.1, «Полугруппы и специализированные аксиомы», стр. 114–116.

Дальнейшее чтение

Чизуэлл, Ян (2008), Курс формальных языков, автоматов и групп , Springer, ISBN 978-1-84800-939-4 .

[1] Эпштейн, Дэвид Б.А .; Кэннон, Джеймс В .; Холт, Дерек Ф.; Леви, Сильвио В.Ф.; Патерсон, Майкл С .; Терстон, Уильям П. (1992), Текстовая обработка в группах , Бостон, Массачусетс: Jones and Bartlett Publishers, ISBN 0-86720-244-0 .

[2] Эпштейн и др. (1992) , Раздел 2.3, «Автоматические группы: Определение», стр. 45–51.

[3] Эпштейн и др. (1992) , раздел 2.4, «Инвариантность при замене генераторов», стр. 52–55.

[4] Эпштейн и др. (1992) , Теорема 2.3.10, с. 50.

[5] Кэмпбелл, Колин М.; Робертсон, Эдмунд Ф.; Рускуц, Ник; Томас, Ричард М. (2001), «Автоматические полугруппы» (PDF) , Theoretical Computer Science , 250 (1–2): 365–391, doi : 10.1016/S0304-3975(99)00151-6

[BrinkAndHowlett-6] Бринк и Хоулетт (1993), «Свойство конечности и автоматическая структура групп Кокстера», Mathematische Annalen , 296 , Springer Berlin/Heidelberg: 179–190, doi : 10.1007/bf01445101 , ISSN 0025-5831 , S2CID 122177473 .

[7] Бирже, Жан-Камиль (2000), Алгоритмические проблемы в группах и полугруппах , Тенденции в математике, Биркхойзер, с. 82, ISBN 0-8176-4130-0

[charney-8] Jump up to: ^а ^б Чарни, Рут (1992), «Группы Артина конечного типа биавтоматичны», Mathematische Annalen , 292 : 671–683, doi : 10.1007/BF01444642 , S2CID 120654588

[9] Хусаинов, Бахадыр; Рубин, Саша (2002), Некоторые мысли об автоматических структурах , CiteSeerX 10.1.1.7.3913

[10] Эпштейн и др. (1992) , Раздел 6.1, «Полугруппы и специализированные аксиомы», стр. 114–116.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]