Введение к работе
1.1 Актуальность темы
ОДНИМ ИЗ ОСНОВНЫХ ТІПІОП ДИСКреТНЫХ упраПЛЯЮПШХ C1ICTC1
являются конечные автоматы. 13 дискретной математике паж мое место занимают так называемые группы автоматных перс ста.новок: группа. /)Sn, состоящая ил всех дсчермшшрованпы: функций одной переменной, биективных па каждом множеств» /';* всех слов фиксированной длины к, составленных из букв ал фанита, f'Jn — {(),1,---,7( — 1} п ее подгруппа из ограниченно детерминированных функций - ASn. (См. Кудрявцев Н.Б., Лле шин СВ., Подколзип Л.С. Введение в теорию автоматов. - М. Паука, 1985). Группа ASn занимает заметное место не только і теории автоматов, она также оказалась хорошей моделью дл> решения ряда, известных проблем теории групп. (См. Каргапо .нов М.И., Мерзляков 10.И. Основы теории групп. - М. : Паука 1982). Одной из важнейших в теории функциональных систем является задача, выразимости и ее частный случай - вопрос с порождающих системах и их свойствах. Рассмотрению этих и связанных с ними вопросов для групп автоматных перестановок и посвящена, данная работа..
1.2 Цель работы
Целью дайной работы является дальнейшее изучение упомянутых выше групп автоматных перестановок и некоторых их важнейших подгрупп (/1/),). и AZn, их определение будет приведено далее) и решение проблемы о существовании в группе ASn (а также в группах Л1)п,Л%п) порождающей системы из элементов бесконечного порядка. Кроме того, исследуются свойства некоторых других порождающих систем в этих группах, а также вопросы, связанные с определением порядков автоматных отображений.
1 : і I
1.3 Научная новизна ' t
В настоящей работе впервые доказано существование порождающих систем из элементов бесконечного порядка в автоматных группах ASn (основной результат работы), ADn,AZ„, Впервые доказано, что в группе AS-i для любого натурального значения к существует автомат, имеющий ровно к состояний на диаграмме Мура, в которых реализуется нетождественная выходная функция, и являющийся автоматом порядка'і*''"1"1. Заметим, что построение подобного примера даже в случае к = 1 (автомат А - го порядка с одним отрицанием на диаграмме) сопряжено с весьма значительными трудностями. Полученный результат проясняет свойства одной важной порождающей системы группы ASn ( эта система S{ii) определена ниже).
1.4 Практическая ценность
Работа носит теоретический характер. Ее результаты и методы могут найти применение при дальнейшем изучении групп автоматных перестановок, а также при решении задач выразимости в классах конечных автоматов или детерминированных функций, или в теории групп.
1.5 Методика исследования
В работе использованы методы теории графов, теории групп, линейной алгебры, топологии и, собственно, методы теории автоматов.
1.6 Апробация работы
Результаты работы докладывались па \\ Всесоюзном (1990) и 4 Межгосударственном (J 993) семинаре но дискретной математике и ее приложениям и па семинарах и МГУ им. М.В. Ломоносова : по теории автоматов под руководством проф., акад. ЛТП В.Б. Кудрявцева, семинаре проф. В.М. Сидельпикова.
1.7 Публикации
Основные результаты опубликованы » работах ангора, список которых приведен и конце автореферата.
1.8 Объем и структура работы