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

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

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

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

Свойство быть автоматическим не зависит от набора генераторов. ^[3]

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

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

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

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

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

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

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

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

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

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

Вот несколько примеров:

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

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

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

Ссылки

1. Эпштейн, Дэвид BA ; Кэннон, Джеймс У .; Холт, Дерек Ф.; Леви, Сильвио В.Ф.; Патерсон, Майкл С .; Терстон, Уильям П. (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) , Теоретическая информатика , 250 (1–2): 365–391, doi : 10.1016/S0304-3975(99)00151-6
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
8. Charney, Ruth (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.

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

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