Автоматическая группа - Википедия - Automatic group
В математика, автоматическая группа это конечно порожденная группа оснащен несколькими конечные автоматы. Эти автоматы представляют собой Граф Кэли группы. То есть они могут определить, находится ли данное словесное представление элемента группы в «канонической форме», и могут определить, отличаются ли два элемента, заданные в канонических словах, генератором.[1]
Точнее, пусть грамм быть группой и А - конечный набор образующих. Затем автоматическая структура из грамм относительно А представляет собой набор конечных автоматов:[2]
- то словообразователь, который принимает для каждого элемента грамм хотя бы одно слово в представляющий его;
- множители, по одному для каждого , которые принимают пару (ш1, ш2), для слов шя принято слово-акцептором именно тогда, когда в грамм.
Свойство автоматизма не зависит от набора генераторов.[3]
Характеристики
Автоматические группы имеют проблема со словом разрешима за квадратичное время. Более того, данное слово может быть фактически преобразовано в каноническую форму за квадратичное время, на основании чего проблема слова может быть решена путем проверки того, представляют ли канонические формы двух слов один и тот же элемент (используя множитель для ).[4]
Автоматические группы характеризуются собственность попутчика.[5] Позволять обозначить расстояние между в графе Кэли . Потом, грамм автоматический по отношению к акцептору слова L тогда и только тогда, когда есть постоянная так что для всех слов которые отличаются не более чем на один генератор, расстояние между соответствующими префиксами ты и v ограничен C. Другими словами, куда для k-го префикса (или же сам, если ). Это означает, что при синхронном чтении слов можно отслеживать разницу между обоими элементами с конечным числом состояний (окрестность тождества диаметром C в графе Кэли).
Примеры автоматических групп
В автоматические группы входят:
- Конечные группы. Чтобы убедиться в этом, возьмем обычный язык за набор всех слов конечной группы.
- Евклидовы группы
- Все конечно порожденные Группы Кокстера [6]
- Геометрически конечные группы
Примеры неавтоматических групп
Биавтоматические группы
Группа это двуавтоматический если он имеет два автомата умножения, для левого и правого умножения на элементы порождающего набора соответственно. Двуавтоматическая группа явно автоматическая.[7]
Примеры включают:
- Гиперболические группы.[8]
- Любой Группа Артина конечного типа, включая группы кос.[8]
Автоматические конструкции
Идея описания алгебраических структур с помощью конечных автоматов может быть обобщена с групп на другие структуры.[9] Например, это естественно обобщается на автоматические полугруппы.[10]
Рекомендации
- ^ Эпштейн, Дэвид Б.А.; Кэннон, Джеймс У.; Холт, Дерек Ф .; Леви, Сильвио В. Ф .; Патерсон, Майкл С.; Терстон, Уильям П. (1992), Обработка текста в группах, Бостон, Массачусетс: Издательство "Джонс и Бартлетт", ISBN 0-86720-244-0.
- ^ Эпштейн и др. (1992), Раздел 2.3, «Автоматические группы: определение», стр. 45–51.
- ^ Эпштейн и др. (1992), Раздел 2.4, «Инвариантность относительно замены образующих», стр. 52–55.
- ^ Эпштейн и др. (1992), Теорема 2.3.10, с. 50.
- ^ Кэмпбелл, Колин М .; Робертсон, Эдмунд Ф .; Рускук, Ник; Томас, Ричард М. (2001), «Автоматические полугруппы» (PDF), Теоретическая информатика, 250 (1–2): 365–391, Дои:10.1016 / S0304-3975 (99) 00151-6
- ^ Бринк и Хоулетт (1993), "Свойство конечности и автоматическая структура для групп Кокстера", Mathematische Annalen, Springer Berlin / Heidelberg, Дои:10.1007 / bf01445101, ISSN 0025-5831.
- ^ Бирже, Жан-Камиль (2000), Алгоритмические проблемы в группах и полугруппах, Тенденции в математике, Birkhäuser, p. 82, ISBN 0-8176-4130-0
- ^ а б Чарни, Рут (1992), «Группы Артина конечного типа биавтоматичны», Mathematische Annalen, 292: 671–683, Дои:10.1007 / BF01444642
- ^ Хусаинов, Бахадыр; Рубин, Саша (2002), Некоторые мысли об автоматических структурах, CiteSeerX 10.1.1.7.3913
- ^ Эпштейн и др. (1992), Раздел 6.1, «Полугруппы и специализированные аксиомы», стр. 114–116.
дальнейшее чтение
- Чисуэлл, Ян (2008), Курс формальных языков, автоматов и групп, Спрингер, ISBN 978-1-84800-939-4.