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

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

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

  • то словообразователь, который принимает для каждого элемента грамм хотя бы одно слово в представляющий его;
  • множители, по одному для каждого , которые принимают пару (ш1ш2), для слов шя принято слово-акцептором именно тогда, когда в грамм.

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

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

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

Автоматические группы характеризуются собственность попутчика.[5] Позволять обозначить расстояние между в графе Кэли . Потом, грамм автоматический по отношению к акцептору слова L тогда и только тогда, когда есть постоянная так что для всех слов которые отличаются не более чем на один генератор, расстояние между соответствующими префиксами ты и v ограничен C. Другими словами, куда для k-го префикса (или же сам, если ). Это означает, что при синхронном чтении слов можно отслеживать разницу между обоими элементами с конечным числом состояний (окрестность тождества диаметром C в графе Кэли).

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

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

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

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

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

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

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

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

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

  1. ^ Эпштейн, Дэвид Б.А.; Кэннон, Джеймс У.; Холт, Дерек Ф .; Леви, Сильвио В. Ф .; Патерсон, Майкл С.; Терстон, Уильям П. (1992), Обработка текста в группах, Бостон, Массачусетс: Издательство "Джонс и Бартлетт", 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, Дои:10.1016 / S0304-3975 (99) 00151-6
  6. ^ Бринк и Хоулетт (1993), "Свойство конечности и автоматическая структура для групп Кокстера", Mathematische Annalen, Springer Berlin / Heidelberg, Дои:10.1007 / bf01445101, ISSN  0025-5831.
  7. ^ Бирже, Жан-Камиль (2000), Алгоритмические проблемы в группах и полугруппах, Тенденции в математике, Birkhäuser, p. 82, ISBN  0-8176-4130-0
  8. ^ а б Чарни, Рут (1992), «Группы Артина конечного типа биавтоматичны», Mathematische Annalen, 292: 671–683, Дои:10.1007 / BF01444642
  9. ^ Хусаинов, Бахадыр; Рубин, Саша (2002), Некоторые мысли об автоматических структурах, CiteSeerX  10.1.1.7.3913
  10. ^ Эпштейн и др. (1992), Раздел 6.1, «Полугруппы и специализированные аксиомы», стр. 114–116.

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

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