О порождающих системах групп автоматных перестановок тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ км. Н. Г. ЧЕРНЫШЕВСКОГО МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

-.6 ОД

( ,, .., На правах рукописи

<- <- L-L.il 'ЦЛ'л

УДК 519.713.2

МАКАРОВ ВЛАДИМИР ВЛАДИМИРОВИЧ

О ПОРОЖДАЮЩИХ СИСТЕМАХ ГРУПП АВТОМАТНЫХ ПЕРЕСТАНОВОК

01.01.09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата фичико - математических наук

САРАТОВ- 1998

Работа выполнена на кафедре математической теории интеллектуальных систем механико - математического факультета МОСКОВСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА им. М. В. Ломоносова

Научный руководитель: доктор физико - математических

наук, доцент C.B. Алешин.

Официальные оппоненты : академик РАЕН, доктор технических

наук, профессор Саратовского государственного университета Твердохлебов Владимир Александрович,

кандидат физико - математических наук, доцент Саратовской государственной

экономической академии Богомолов Сергей Анатольевич

Ведущая организация : Московский энергетический институт

Защита^ диссертации состоится « /-> » оК-7~Л<ГРЛ 1998 года в « ^Ь » часов на заседании специализированного Совета К 063.74.04 в Саратовском государственном университете им. Н. Г. Чернышевского по адресу : 410601, г. Саратов, ул. Астраханская, 83.

С диссертацией можно ознакомиться в библиотеке Саратовского государственного университета.

Автореферат разослан « Т » аилТл ^ 1998 года.

Ученый секретарь специализированного Совета, кандидат физико - математических наук,

доцент щ/^^СОЩ! П. Ф. Недорезов

1 Общая характеристика работы

1.1 Актуальность темы

Одним из основных гипоп дискретных управляющих снстс! являются конечные автоматы. 13 дискретной математике вал< мое место занимают так называемые группы автоматных перс стапоиок: группа /Л'*',,., состоящая ил всех дечермшшроианпы: функций одной переменной, биективных па каждом множеств« всех слои фиксированной длимы к, состамленных из бук» ал фавита, Нп = {0,1, ■ ■ ■ — 1} и се подгруппа из ограниченно детерминированных функций - Л5„. (См. Кудрявцев Н.Б., Ллс шип С.В., Подколзип Д.С. Введение и теорию автоматов. - М. Паука, 1985). Группа ЛИп занимает заметное место не только I теории автоматов, она также оказалась хорошей моделью дл> решения ряда, известных проблем теории групп. (См. Каргапо .нов М.И., Мерзляков 10.И. Основы теории групп. - М. : Паука 1982). Одной из важнейших в теории функциональных систем является задача, выразимости и ее частный случай - вопрос с порождающих системах и их свойствах. Рассмотрению этих и связанных с ними вопросов для групп автоматных перестановок и посвящена, данная работа.

1.2 Цель работы

Целью данной работы является дальнейшее изучение упомянутых выше групп автоматных перестановок и некоторых их важнейших подгрупп (Л 1)п и Л7/п, их определение будет приведено далее) и решение проблемы о существовании в труппе ЛБп (а также в группах Лип,Л%п) порождающей системы из элементов бесконечного порядка. Кроме того, исследуются свойства некоторых других порождающих систем в этих группах, а также вопросы, связанные с определением порядков автоматных отображений.

л ■ /

1.3 Научная новизна /

В настоящей работе впервые доказано существование порождающих систем из элементов бесконечного порядка в автоматных группах ЛЯп (основной результат работы), ADn,AZn. Впервые доказано, что в группе Л52 для любого натурального значения к существует автомат, имеющий ровно к состояний па диаграмме Мура, 11 которых реализуется нетождественная выходная функция, и являющийся автоматом порядка ' '. Заметим, что построение подобного примера даже в случае к = 1 (автомат 4 - го порядка с одним отрицанием па диаграмме) сопряжено с весьма значительными трудностями. Полученный результат проясняет свойства одной важной порождающей системы группы А5'п ( эта система 5'(и) определена ниже).

1.4 Практическая ценность

Работа носит теоретический характер. Ее результаты и методы могут найти применение при дальнейшем изучении групп автоматных перестановок, а также при решении задач выразимости в классах конечных автоматов или детерминированных функций, или в теории групп.

1.5 Методика исследования

В работе использованы методы теории графов, теории групп, линейной алгебры, топологии и, собственно, методы теории автоматов.

1.6 Апробация работы

Результаты работы докладывались па Всесоюзном (1990) и 4 Межгосударственном (1993) семинаре но дискретной математике и ее приложениям п па семинарах п МГУ им. М.В. Ломоносова : по теории автоматов под руководством проф., акад. ЛТП В.Б. Кудрявцева, семинаре проф. В.М. Сидельпикоиа.

1.7 Публикации

Основные результаты опубликованы » работах ангора, список которых приведен и конце автореферата.

1.8 Объем и структура работы

Работа изложена на 70 страницах машинописного текста и состоит из оглавления, введения, пяти глав и 15 рисунков. Первая глава состои т из 2 параграфов, вторая, третья, четвертая, пятая - содержат по параграфа каждая. Библиография включает и себя 29 наименований.

2 Содержание работы

Во Введетш определяются основные понятия, приводятся некоторые из наиболее важных результатов, полученных другими авторами, приводятся основные результаты работы.

Пусть п - целое число, и > 2. Пусть 1']а — {0, 1, • • •, п — 1 }. Кольцо вычетов, состоящее из всех элементов множества /£„, с операциями Ф,0, обозначается, как обычно, через Zn. Пусть Sn - полная симметрическая группа всех перестановок J(x) па множестве А'„. Юсли /,<у G Sa, то обозначим J(:c)(j(x) = g(f(%))-Пусть т(х) - перестановка из Sn такая, что т(0) = 1,т(1) = (),т(<г) = а при a (¡l l'J2- Как известно, перестановки т(л;),:гф 1 порождают группу Sn.

Группа А1)п автоматных перестановок состоит из всех одноместных детерминированных функции, заданных инициальными автоматами Л вида А = ( /'Jn, Q. /'Jn,ip,^.>,ïv), где l'Jn - алфавит входных и выходных символов, Q - не обязательно конечное множество состояний, ip : Q х Еп —» Q - (функция переходов, ф : Q х Fj,i —> i'a - функция выходов, in - начальное состояние, причем автомат Л должен обладать свойством:

V*/ G Q3m„ G ип(ф{ч,х) = X фт(|).

Подгруппа и Л1)п, состоящая из ограниченно - детерминированных функций, обозначается через AZn. Заметим, что AZn

;î

«•.одержит бесконечную конечно - порожденную периодическую подгруппу (Результат С.П. Алешина).

Группа ОЬ'п автоматных перестановок состоит из и сох одноместных детерминированных функций, заданных инициальными автоматами Л ни да А — (Еп, С^, /','„, </?, ф, го), обладающими свойством:

Уч еЯ^/Л') < -г)- /,,(.,■)).

Подгруппа в состоящая из ограниченно - детерминиро-

ванных фупкциИ, обозначается через АНп.

Верпы следующие групповые включения:

П8п 3 /1.9» I) АЪп, 1)$п 3 Л1)п з ЛЯ„.

Пусть Т>п = {А = 1Сп,<р,ф,\1>) £ ЛБп :

3</ € ОЧщ €СШФ(<1, *) = -г (1) 1) А ((г/, = <,) V (*/>('/,,.т) = •'■•)))}•

Таким образом, в систему 'Р„ входят те а.втоматы из ЛЬ'п, па, диаграмме Мура которых лишь и единственном состоянии реализуется функция х (1) I, а. и остальных состояниях реализуется тождественная функция входа.

Пусть тп = {л = (/о,,., д, /-;„,<,£),V','«) е лнп ■.

эч е = т(.т)) А ((,/, = <,) V (ф{ъ,х) = .г)))}.

Таким образом, в систему Тп входят то а.втоматы из АБпл па. диаграмме Мура которых лишь в единстпепном состоянии реализуется функция г (я;), а. и остальных состояниях реализуется тождественная функция входного значения.

Пусть также ¿¡"('О = и Тп.

Нерез Е™ мы обозначим множество всех слов длины т, состоящих из букв алфавита. 1С,,. Через Е* мы обозначим множество всех слов конечной длины, составленных из элементов алфавита Еп. Суперпозицию автоматных отображений А и Е обозначим как А о И и будем считать: если С = А о И, то при любом а 6 Е* имеет место С {а) = В(Л(а)).

1] Главе 1 изучаются топологические характеристики групп автоматных перестановок, впервые исследованные в работе:

\

Чакапь 15., Гечег 'I'. О группе «.»томатных перестановок. - Кибернетика., НК)Г), Пып. Г).

Они бывают полезны при прояснении ряда автоматных и теоретико - групповых свойств антоматных групп. В определенной метрике дискретными подг руппами являются липп, конечные подгруппы Л 0-2, есть о ткры то - замкнутые множества, компакт-пая группа. Л 1)г не яилжтся группой Ли (как локально компактная группа, п каждой окрестности единицы которой содержится нетривиальная подгруппа). Мели рассматривать группу ЛП-2 как функциональную систему с. алгебраической операцией суперпозиции и топологической операцией замыкания (то есть с оператором А - полноты), то элемен ты порядка. 2 порождают

л/;,.

Заметим также, что неизвестно, порождают ли все элементы порядка 2 группу Л5'2-

13 Главе 2 рассмотрены некоторые свойства. конечных подгрупп групп Л1)2,Л8г-

13 Теореме 2.'5.1 приводится одно интересное достаточное услоние бесконечности порядка автомата из Г])уппы Л.

Пусть А £ Ли задан диаграммой с алфавитом состояний = {I, •••,?(.}, причем п состояниях из множества М\ = { 1, • • ■, к} реализуется о трицание входного значения, а. п остальных состояниях - тождественная функция входного значения. Пусть 1 - начальное состояние. Пусть при произвольном I > 2 определено М, = {I £ С,) : 3щ £ (</?('', <ц) € М<-\, <£>(?', <4 СО 1) ^

Очевидно, что для любого (, М( С С}, следовательно, последовательность {М/} (называемая гомологической ) является периодической.

Теорема 2.3.1. Пусть гомологическая последовательность автомата. Л имеет вид:

А/,, • • ■, Л7Г, Л/,, • • •, Мг, • • •.

гГогда, автомат А имеет бесконечный порядок.

И Главе 3 рассмотрены свойства порождающей системы 5" = ¿'(2) группы А9г.

Отметим, что вопрос о том, автома ты каких порядков входят в систему 5(7?.), является открытым даже для случая и = 2 ( в

> .

/' 'V

л- .. /

t

:лучае п = 2 множества Т>п и Тп совпадают). В группе AS-¿ все шементы конечного порядка имеют порядки, являющиеся сте-юнями 2. Известно, что система S{2) содержи т элементы пер-юго, второго, четвертого (результат автора [1]) и бесконечного юрядка. Неизвестно, содержатся ли в системе ,S'(2) элементы саких - либо других порядков (например, восьмого).

Заметим, что если Aj 6 S(2) и A¡ ф Е, где Е - единица автоматной группы, Л] = (E-¿, {1, • • • , п}, Е2, <р, ф, го), ф(1, х) = с ф 1, то автомат Ло = (Е?, {1, • • •, vi], i'J2, f, ф, 1) имеет порядок, эавный порядку автомата Л{.

Пусть для ß £ через (¡ß обозначено состояние, в которое гвтомат Л0 переходит из начального состояния 1 но входному :лову ß.

Пусть Ло - элемент системы S(2), 1 - начальное состояние А о и в этом состоянии реализуется нетождественная выходная функция ф( 1,х) = i' Ш 1. Предположим, что автомат Ло имеет юрядок, больший 2: |Ло| > 2. Очевидно, что для автомата Ло = [Е2, {1, • • • ,п}, 1) выполнено следующее:

З7 Е E¡36 £ 1'п(<1бу = 1, <7л()(й7) ф О-

Из всех слов 7, обладающих вышеприведенным свойством, иыберем слово наименьшей длины (таких, вообще говоря, несколько) и обозначим его через п. Это слово а назовем разделяющим. Пе ограничивая общности, можно считать, что 8 = 0.

Очевидно:

</о« = ф 1,Л0(Опг) = lfv, Л„(1а) = 0 а.

Имеет место ((»акт, полученный автором в параграфе 2:

Если порядок автомата Ли равен то автомат Л() имеет следующую орбиту мощности 4 из сверхслов 7ÍUU, //01,^10,^11 Для каждого разделяющего слова, о :

Лцб = («Ш^Ф1) « (aai l>a¿) {(ш:i ba,t) ■ ■ •

(««2А.--1 l>(*ik) ' ■ • ,

et, Ь £ Е>,

где

- некоторые начальные фрагменты слона ("V.

Используя нышеп ринедеп ну ю Лемму, можно построить эле мент системы ,4(2) четвертого порядка. Диаграмма этого ан томата (минимальный но числу состояний па диаграмме Мур; элемент 4 - го порядка системы Я(2) имеет 8 состояний) пршю дится и работе и нерна следующая:

Теорема 3.3.2 В группе /1,9-2 для проипюлыюго натурального числа 1с существует автомат, имеющий ровно к отрицай и ( на диаграмме Мура порядка

Н Глава доказаны теоремы ([4]):

Теорема 4.2.1 Группа /1.$2 порождается элементами беско печного порядка.

Теорема 4.3.1 Группа А порождается элементами бесконечного порядка.

Главе 5 рассмотрены груши»! перестановок ЛЪ'п, Л1)п, Л2п ОЬ'а при ПрОП'ЗИОЛЬПОМ II.

При л 6 /£* через а00 обозначим сверхслопо: па • ■ • а ■ ■ ■.

Лемма 5.2.1 Пусть А в 1)Ь'п. Пусть XV = {а0°° : а е Е*}. Пусть сущестнует £ множества снерхслоп XV, такое, что значение /1(£) отображения А на сиерхслоие £ не принадлежит XV, но для любого г] из XV имеет место /1~'(//) € IV, то есть обратное к А отображение Л-1 сохраняет множество XV. Тогда отображение А имеет бесконечный порядок.

Теорема 5.2.1 Группа А2п порождается элементами бесконечного порядка.

Теорема 5.2.2 Группа А1Уп порождается элементами бесконечного порядка.

Лемма 5.3.1 Мпожестио Я(п) является порождающей системой для группы А5',,.

Основная теорема работы ([(>]):

Теорема 5.3.1 Группа /1Л'П порождается элементами бесконечного порядка.

Заметим, что мы эффектнпным образом построили порождающую систему из элементов бесконечного порядка для групп АЬ'п, А'Ап (сущестнует алгоритм, определяющий принадлежносп

произвольного автомата группы предложенным порождающим сисчемам, состоящим из элеменчou бесконечного порядка,).

Однако неизвестно, существует ли эффективная процедура, определения порядка, произвольного конечного автомата, даже в группе /1S2•

Автор выражает благодарность Алешину C.B. за. руководство работой и Кудрявцеву В.1>. за цепные советы по представлению результатов и многочисленные консультации.

Список работ, содержащих основные результаты диссертации:

1. Макаров В.В. О порядках элементов группы автоматных перестановок. - Вестник МГУ. Сер.1. Мат.,мех., 1991., Выи.■I., С. 8(1 - 87.

2. Макаров В.В. О топологических свойствах группы автоматных перестановок. - Алгебра., геометрия и дискретная математика в нелинейных задачах., МГУ, 1991, С. 91 - 97.

3. Макаров В.В. Порождающая система, из элементов бесконечного порядка в группе автоматных перестановок AS,,. - Ден. в ВИНИТИ, 1995, 3294 -В95, С. I - Hi.

4. Макаров В.В. О группах автоматных перестановок. -Фундаментальная и прикладная математика. - 1996. - Том 2. -Вып.1. - С. 171 - 18С.

5. Макаров В.В. О топологических характеристиках автоматных групп. - Сборник трудов семинара, по дискретной математике и ее приложениям., МГУ, 1997, С. 143 - MG.

G. Макаров В.В. Группа ав томатных перестановок ASn порождается элементами бесконечного порядка. - Дискретная математика., 1997, Том 9, Вып.З.