О вычислении системы переписывающих правил в конечной группе | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/39

О вычислении системы переписывающих правил в конечной группе

Представлен алгоритм, определяющий переписывающую систему конечной группы, заданной фиксированным порождающим множеством. Необходимым условием эффективной реализации алгоритма является наличие быстрой процедуры умножения элементов в группе. Такой групповой операцией может быть композиция подстановок, умножение матриц, вычисление полиномов Холла и т.д. Алгоритм был применён для исследования переписывающих систем в конечных дву-порождённых группах периода 5.

Computation of rewriting systems in finite groups.pdf Решение некоторых задач теории кодирования и криптографии сводится к исследованию подходящих графов Кэли, например открытая проблема эффективного восстановления вершин в графе Хэмминга [1]. Поиск кратчайших путей в графах Кэли является труднорешаемой проблемой, поэтому исследователям приходится идти на различные уловки и приёмы, чтобы получить решение за приемлемое время. Например, в [2] сначала определяют автоматическую структуру группы, которая порождает соответствующий граф Кэли. Автоматическая структура группы состоит из конечных автоматов специального вида [3]. Для их вычисления требуется определить множество соотношений в группе, используя известный алгоритм Кнута - Бендикса [4]. Зачастую алгоритм Кнута - Бендикса работает недопустимо долго, например в конечных группах, заданных коммутаторными соотношениями. В этом случае разворачивание коммутаторных соотношений приводит к очень длинным словам, что катастрофически замедляет работу алгоритма. Настоящая работа представляет собой попытку устранить указанный недостаток. Остановимся подробнее на основных определениях. Пусть G = (X) - конечная группа, порождённая упорядоченным множеством X = {x1 - x2 - ... - xm}, которое также называют алфавитом. Множество всех слов (строк) над алфавитом X будем обозначать X*. Пусть w = x1x2 ... x - слово над X и |w| = l -его длина. На множестве X* также определим отношение порядка. Пусть v и w - два произвольных слова в алфавите X. Тогда v - w, если |v| < |w|, а в случае равенства длин меньшее слово определяется согласно введённому лексикографическому порядку на порождающих. Если необходимо подчеркнуть, что строка v G X* соответствует элементу g G G, то будем писать vg. Строку v будем называть минимальным словом элемента g, если для всех других w G X*, таких, что vg = wg, выполняется v - w. Очевидно, что каждому g G соответствует уникальное минимальное слово. Единице группы e соответствует пустое слово е: |е| = 0. Пусть R - система переписывающих правил (переписывающая система), состоящая из множества пар вида (u,v), где ug = vg и u У v [4]. При этом слово u называют левой стороной правила, а строку v - правой. Иногда правила записывают в виде u ^ v. Действие системы R над некоторым словом w означает осуществление замен вида xuy ^ xvy до тех пор, пока не будет получено несократимое относительно R слово w', т. е. R(w) = w'. Если изменение порядка применения правил не влияет на конечный результат, то R называют конфшюэншной. Переписывающую систему R называют несократимой, если для любой пары (u, v) G R выполняется R'(u) = u и R'(v) = v, где R' = R \\ {(u, v)}. Алгоритм 1 определяет переписывающую систему конечной группы G = (X, о). Необходимым условием эффективной реализации алгоритма является наличие быстрой процедуры умножения элементов в группе. Например, групповой операцией о может быть композиция подстановок, умножение матриц, вычисление полиномов Холла и т. д. Алгоритм 1. R = RewritingSystem(G, X, о) Вход: G = (X, о). Выход: система переписывающих правил R группы G. 1: Po := {е} -множество минимальных слов. 2: K0 := {(e, е)} - словарь вида (элемент группы, его минимальное слово). 3: R := 0. 4: Для всех i = 1, 2,... , то: 5: K, := Ki-1, P, := 0. 6: Для всех x G X и р G Pi-1: 7: u := xp - конкатенация слов, 8: g := x о р - групповое умножение. 9: Если g G K,, то 10: если R(u) = u, то v := K,[g], добавить (u,v) в R, 11: иначе 12: добавить u в P,, добавить (g,u) в Ks. 13: Если P, = 0, то 14: Вернуть R. Теорема 1. Пусть R - система переписывающих правил, полученная при помощи алгоритма 1, тогда R конфлюэнтна и несократима. Рассмотрим примеры. Пусть B0(2,5) = (a1,a2) -наибольшая конечная двупо-рождённая бернсайдова группа периода 5, порядок которой равен 534 [5]. Для каждого элемента данной группы существует уникальное коммутаторное представление вида а^1 ■ а22 ■ ••• ■ а"44, где a G Z5, i = 1, 2,..., 34. Здесь а! и а2 -порождающие элементы B0 (2, 5), а3,...,а34 - коммутаторы, которые вычисляются рекурсивно через ai и а2. Определим фактор-группу группы B0(2,5) следующего вида: Bk = Bo(2, 5)/(а*;+1,... ,аэ4). Очевидно, что |Bfc| = 5k. Пусть Rk - переписывающая система группы Bk. На рис. 1 представлены графики роста Rk для минимального порождающего множества X = (а1,а2), а также симметричного Y = (а1,а2, а-1, а-1). се' ' О-1-1-1-1-1- 2 4 6 8 10 12 14 к Рис. 1. Графики роста соотношений в Bk

Ключевые слова

система переписывающих правил, группа Бернсайда, Burnside group, the rewriting system

Авторы

ФИООрганизацияДополнительноE-mail
Кузнецов Александр АлексеевичСибирский государственный университет науки и технологий имени академика М.Ф. Решетнёвадоктор физико-математических наук, профессор, директор институтаalex_kuznetsov80@mail.ru
Всего: 1

Ссылки

Константинова Е. В. Комбинаторные задачи на графах Кэли. Новосибирск: НГУ, 2010. 110с.
Camelo M., Papadimitriou D., Fabrega L., and Vila P. Efficient routing in Data Center with underlying Cayley graph // Proc. 5th Workshop Complex Networks CompleNet. 2014. P. 189197.
Epstein D., Paterson M., Cannon J., et al. Word Processing in Groups. Boston: Jones and Barlett Publ., 1992. 330 p.
Sims C. Computation with Finitely Presented Groups. Cambridge: Cambridge University Press, 1994. 628 p.
Havas G., Wall G., and Wamsley J. The two generator restricted Burnside group of exponent five // Bull. Austral. Math. Soc. 1974. No. 10. P. 459-470.
 О вычислении системы переписывающих правил в конечной группе | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/39

О вычислении системы переписывающих правил в конечной группе | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/39