Jump to content

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

(Перенаправлено из группы «Биавтоматика» )

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

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

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

Свойство автоматизма не зависит от набора образующих. [3]

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

[ редактировать ]

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

[ редактировать ]

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

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

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

[ редактировать ]

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

  1. ^ Эпштейн, Дэвид Б.А .; Кэннон, Джеймс В .; Холт, Дерек Ф.; Леви, Сильвио В.Ф.; Патерсон, Майкл С .; Терстон, Уильям П. (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) , Theoretical Computer Science , 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. ^ Jump up to: а б Чарни, Рут (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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 8f950488d6db4485128174f04b0eafff__1699828380
URL1:https://arc.ask3.ru/arc/aa/8f/ff/8f950488d6db4485128174f04b0eafff.html
Заголовок, (Title) документа по адресу, URL1:
Automatic group - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)