Автоматическая группа
В математике автоматическая группа — это конечно порожденная группа, оснащенная несколькими автоматами с конечным числом состояний . Эти автоматы представляют собой граф Кэли группы. То есть они могут определить, находится ли данное словесное представление элемента группы в «канонической форме», и могут определить, отличаются ли два элемента, заданные в канонических словах, генератором. [1]
Точнее, пусть G — группа, а A — конечное множество образующих. Тогда автоматическая структура группы G относительно A представляет собой набор конечных автоматов: [2]
- , акцептор слова который принимает для каждого элемента G хотя бы одно слово из представляющий его;
- множители , по одному на каждый , которые принимают пару ( w 1 , w 2 ) для слов w i, принимаемых акцептором слова, именно тогда, когда в Г.
Свойство автоматизма не зависит от набора образующих. [3]
Характеристики
[ редактировать ]В автоматических группах есть словесная задача , решаемая за квадратичное время. Более строго, данное слово действительно может быть приведено в каноническую форму за квадратичное время, на основе чего проблема слов может быть решена путем проверки того, представляют ли канонические формы двух слов один и тот же элемент (используя множитель для ). [4]
Автоматические группы характеризуются свойством попутчика . [5] Позволять обозначают расстояние между в графе Кэли . Тогда группа G автоматична по отношению к акцептору слова L тогда и только тогда, когда существует константа такой, что для всех слов которые отличаются не более чем на один генератор, расстояние между соответствующими префиксами u и v ограничено C . Другими словами, где для k-го префикса (или сам, если ). Это означает, что при синхронном чтении слов можно отслеживать разницу между обоими элементами с конечным числом состояний (окрестность единицы с диаметром 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 .