WikiDer > Автоматическая группа - Википедия

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

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

• то словообразователь, который принимает для каждого элемента грамм хотя бы одно слово в ${ displaystyle A ^ { ast}}$ представляющий его;
• множители, по одному для каждого ${ Displaystyle а в А чашка {1 }}$, которые принимают пару (ш₁, ш₂), для слов ш_я принято слово-акцептором именно тогда, когда ${ displaystyle w_ {1} a = w_ {2}}$ в грамм.

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

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

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

Автоматические группы характеризуются собственность попутчика.^[5] Позволять ${ Displaystyle д (х, у)}$ обозначить расстояние между ${ displaystyle x, y in G}$ в графе Кэли ${ displaystyle G}$. Потом, грамм автоматический по отношению к акцептору слова L тогда и только тогда, когда есть постоянная ${ Displaystyle C in mathbb {N}}$ так что для всех слов ${ displaystyle u, v in L}$ которые отличаются не более чем на один генератор, расстояние между соответствующими префиксами ты и v ограничен C. Другими словами, ${ 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}}$ для k-го префикса ${ displaystyle w}$ (или же ${ displaystyle w}$ сам, если ${ displaystyle k> | w |}$). Это означает, что при синхронном чтении слов можно отслеживать разницу между обоими элементами с конечным числом состояний (окрестность тождества диаметром C в графе Кэли).

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

В автоматические группы входят:

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

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

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

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

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

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

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

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

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

Рекомендации

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

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