Содержание
Введение 3
1 Основные понятия 10
1.1 Элементы алгебры отношений, теории полугрупп и теории гиперграфов 10
1.2 Гинерграфические автоматы...........................................21
1.3 Обратимые входные сигналы универсальных гииерграфических автоматов............................................................ 23
2 Универсальные гинерграфические автоматы 44
2.1 Определяемое™, гииерграфических автоматов полугруппами их входных сигналов......................................................44
2.2 Конкретная характеризация универсальных гииерграфических
автоматов.......................................................... 48
2.3 Абстрактная характеризация универсальных гииерграфических
автоматов.......................................................... 57
3 Взаимосвязь свойств автоматов и их полугрупп входных сигналов 62
3.1 Относительно элементарная определимость универсальных гииерграфических автоматов в классе полугрупп.....................63
3.2 Элементарная эквивалентность универсальных гииерграфических автоматов............................................................ 87
3.3 Проблемы разрешимости элементарных теорий универсальных гииерграфических автоматов........................................... 89
3.4 Гомоморфизмы универсальных гииерграфических автоматов..94
3.5 Мономорфизмы универсальных гииерграфических автоматов.104
Заключение 124
2
Введение
Работа посвящена развитию алгебраической теории универсальных гиперграфичсских автоматов. Теория автоматов представляет собой один из основных разделов математической кибернетики, главными объектами изучения которой являются устройства, предназначенные для управления динамическими системами, изменяющими свои состояния иод воздействием сигналов из внешней среды. Примерами таких устройств могут служить электронно-вычислительное. телекоммуникационное оборудование. бытовая техника и т.н. Математической моделью таких устройств является автомат А = (X, 5, д). который представляет собой двухосновную алгебраическую систему с двумя основными множествами X, 5 и бипарной операцией 6 : X х 5 —» X. При этом X называется
множеством состояний, 5 множеством входных сигналов, 5 функцией ирореходов автомата. Отображение 8 для каждого фиксированного 5 6 5 определяет соответствующее этому входному сигналу 5 преобразование 5л множества состояний, которое для каждого х £ X указывает состояние 53(х) — 5(х.в), в которое переходит автомат А при входном сигнале 5. Последовательное действие входных сигналов € 5 реализуется композицией преобразований 53, £/. В результате множество 5 можно рассматривать как полугруппу с ассоциативной бинарной операцией *, которая взаимосвязана с функцией переходов автомата но формуле: £(я, з • £) = 6*),/-) для любых х £ X и $,£ £ 5.
В зависимости от специфики рассматриваемых задач математической кибернетики, устройства управления динамическими системами могут моделироваться структуризованиыми автоматами, у которых множества состояний наделены дополнительной математической структурой, сохраняющейся функциями переходов таких автоматов. В качестве таких дополнительных структур могут выступать, например, структуры вероятностного пространства, линейного пространства, топологического пространства, упорядоченного множества и другие. Автоматы, наделенные такими дополнительными структурами, называются |25|, соответственно, вероятностными автоматами, линейными автоматами,
3
топологическими автоматами, упорядоченными автоматами. Исследованиям таких автоматов посвящены известные работы Аблаева Ф.М., Бухараеиа Р.Г., Скорнякова Л.А., Сперанского Д.В., Плоткипа Б.И., Ф. Гсчета, Акимовой С.А. и многих других. При таком подходе структуризовапные автоматы являются объектами исследования алгебраической теории автоматов, которая основывается на фундаментальных понятиях универсальной алгебры [16] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, связанным с их поведением, анализом и синтезом, к теории формальных языков и к другим разделам математической кибернетики [25], [35].
В настоящей работе продолжается исследование структуризоваппых автоматов: здесь рассматриваются так пазЕлваемые гиперграфические автоматы, т.е. автоматы, у которых множества состояний наделены дополнительной алгебраической структурой гиперграфа [12]. Поскольку гиперграфы являются естественным обобщением понятий обыкновенного графа, плоскости [14], |31| и разбиения множества, то изучаемые автоматы образуют достаточно широкий и весьма важный класс автоматов, многообразие которых охватывает, в частности, автоматы, у которых множества состояний являются плоскостями (например, проективными или аффинными), а также автоматы, у которых множества состояний разбиваются на классы некоторой эквивалентности. В работе рассматриваются полугрупповые автоматы, поэтому далее под гиперграфическим автоматом будем понимать полугрупповон автомат А = (X,S,6), у которого множество состояний X наделено такой структурой гиперграфа Н — (X. L), что при любом входном сигнале s € S функция переходов Ss : X —► X является эндоморфизмом гиперграфа Н. Основное внимание в работе уделяется гиперграфическим автоматам, у которых множества состояний являются гиперграфами особого вида эффективными 1’иперграфами с р-опрсдслимыми ребрами. В частности, эффективные гимерграфы с
1-оиределимыми ребрами - это гиперграфы, ребра которых образуют нетривиальное разбиение множества вершин без одноэлементных классов. Кроме того, эффективными гинерграфами с 2-определимыми ребрами являются конечные плоскости - специальные комбинаторные
4
конфигурации, которые имеют важные приложения в таких разделах прикладной математики, как теория планирования экспериментов, теория кодирования и многие другие (см., например, [19]).
Главное внимание в настоящей работе уделяется так называемым универсальным гиперграфическим автоматам. Особый интерес к этой тематике объясняется тем, что понятие универсал ьного объекта играет центральную роль в многочисленных приложениях теории категорий к теории автоматов. Например, минимальные автоматы являются универсальными притягивающими объектами в категориях эквивалентных между собой автоматов. При изучении гиперграфичсских автоматов универсальным притягивающим объектом в катстрии гиперграфичсских автоматов с фиксированным гиперграфом состояний Я является автомат Atm(Я) = (Я, End Я, S) с гиперграфом состояний II = (X,L), полугруппой входных
сигналов End Я (состоящей из эндоморфизмов гиперграфа II) и функцией переходов 5(х,ф) = х) (здесь х £ X, tp £ End Я), который называется универсальным гиперграфическим автоматом и удовлетворяет универсальному свойству: для любого гипсрграфичсского автомата А = (Я, S, S) с гииерграфом состояний Я существует
единственный гомоморфизм по входным сигналам А в Atm(H).
В таком контексте при исследовании автоматов А с гиперграфом состояний Я важную роль играет полугруппа End Я эндоморфизмов гиперграфа II. Поэтому алгебраическая теория универсальных гиперграфичсских автоматов тесно связана с одним из основных разделов современной алгебры - обобщенной теорией Галуа, которая посвящена изучению математических объектов путем исследования некоторых производных алгебр отображений, специальным образом связанных с исходными объектами. В нашем случае изучаемым математическим объектом является универсальный гиперграфичсский автомат Atm(H), производной алгеброй отображений -• его полугруппа входных сигналов End Я. Таким образом, алгебраическая теория гиперграфичсских автоматов тесным образом связана с общеизвестной задачей опродслясмости математических объектов их эндоморфизмами и автоморфизмами, ко'горая сформулирована в числе прочих
актуальных математических проблем в известной книге С. Улама [29).
Проведенные в работе исследования следуют традиционному кругу вопросов обобщенной теории Галуа. Принципиальное значение имеет задача о том, как производная алгебра отображений определяет’ исходный объект; затем исследуется, какими абстрактными свойствами характеризуется такая производная алгебра отображений; наконец, с помощью полученных результатов изучаются взаимосвязи свойств исходного объекта и его производной алгебры отображений. Такие вопросы для полугрупп эндоморфизмов графов, колец линейных преобразований векторных пространств и других алгебр преобразований весьма успешно исследовались Важсниным Ю.М.. Плоткиным В.И., Глускиным Л.М., Михалевым Л.В. и другими авторами. Особое внимание в этом направлении уделялось изучению групп автоморфизмов и полугрупп эндоморфизмов графов, для которых Д. Кениг в |37] сформулировал следующую задачу: каким условиям должна удовлетворять группа подстановок из п элементов, чтобы существовал п-вершшшый граф, группа автоморфизмов которого совпадает с этой группой подстановок? Эта известная и до сих пор не решенная задача является частным случаем сложной проблемы конкретной характеризации [36] производных алгебр отображений в обобщенной теории Галуа, т.с. проблемы описания таких условий, при которых алгебра отображений равна производной алгебре отображений изучаемою математического объекта. В этом направлении отдельные продвижения были сделаны М. Краснером [38], Липиным Е.С. [20|, Б. Йонсоном [36], Бредихиным Д.А. [4] и другими авторами для полугрупп эндоморфизмов рслятивов, групп автоморфизмов и инверсных полугрупп частичных автоморфизмов универсальных алгебр.
Класс универсальных гииерграфичсских автоматов образует категорию, морфизмами которой являются гомоморфизмы таких автоматов. Изучению таких морфизмов в работе уделяется особое внимание, так как гомоморфизмы автоматов играют важную роль в задачах моделирования автоматов [lj, [17], минимизации автоматов [2],
[8], факторизации автоматов [3], [13] и многих других.
Принципиальным отличием проведенных в диссертации исследований
6
является положенное 13 их основу решение задачи конкретной характеризации универсальных гинсрграфических автоматов. Эта задача формулируется следующим образом:
при каких условиях на множестве состояний X автомата А можно так определить структуру гиперграфа Н = (X, L), что будет выполняться равенство А = Atrn(Я), т.е. полугруппа входных сигналов автомата А будет совпадать с полугруппой эндоморфизмов End Я?
Главным инструментом решения сформулированной задачи является разработанная Молчановым В.А. [39] техника канонических отношений полугрупп преобразований, которые определяются в исходных полугруппах формулами языка узкого исчисления предикатов (УИП). Как показывают результаты [23], [39], такое решение поставленной задачи дает эффективный метод последовательного изучения взаимосвязи свойств универсальных структуризованных автоматов и их полугрупп входных сигналов.
В начале первой главы работы приводятся основные понятия теории гиперграфов, алгебры отношений, теории полугрупп и теории автоматов, которые необходимы для последовательного развития алгебраической теории гинсрграфических автоматов. В конце первой главы описываются обратимые входные сигналы универсальных гинерграфичсских автоматов, чьи множества состояний являются аффинными или проективными плоскостями малых размерностей.
Во второй главе диссертации рассматриваются комбинаторные и логико-алгебраические свойства универсальных гинсрграфических автоматов.
В разделе 2.1 исследована задача об абстрактной определяемое™ универсальных гинсрграфических автоматов над эффективными гиперграфами с р—определимыми ребрами своими полугруппами входных сигналов. В разделе 2.2 излагается центральный результат второй главы, который дает решение задачи конкретной характеризации универсальных гинсрграфических автоматов над эффективными гииерграфами с р—определимыми ребрами. В разделе 2.3 получен а абстрактная характеристика универсальных гинерграфи чсских .автоматов над эффективными гииерграфами с р—определимыми
7
ребрами.
В третьей главе диссертации приведены результаты исследования взаимосвязи свойств универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами и полугрупп входных сигналов этих автоматов.
В разделе 3.1 доказана относительно элементарная определимость
[9) класса таких автоматов в классе всех полугрупп. С помощью этого результата в разделах 3.2, 3.3 исследована взаимосвязь важных проблем алгоритмической разрешимости элементарных теорий классов эффективных гиперграфов с р—определимыми ребрами, классов универсальных гиперграфических автоматов над эффективными
гиперграфами с р—определимыми ребрами и классов полугрупп эндоморфизмов этих гиперграфов.
В разделе 3.4 описано строение сюрьективных гомоморфизмов универсальных гиперграфических автоматов над эффективными
гиперграфами с р—определимыми ребрами.
В разделе 3.5 изучается строение мономорфизмов универсальных гиперграфических автоматов над эффективными гиперграфами с
р—определимыми ребрами.
Полученные результаты решают ряд принципиальных вопросов о взаимосвязи гиперграфических автоматов с их полугруппами
входных сигналов, а также дают весьма эффективный инструмент для дальнейшего разностороннего исследования этой проблематики в алгебраической теории автоматов и для разнообразных приложений к комбинаторному исследованию автоматов, к изучению вопросов классификации автоматов средствами языка УИП и к анализу проблем разрешимости элементарных теорий классов автоматов.
В ходе диссертационного исследования был разработан программный продукт "Построение плоскости", предназначенный для построения аффинных и проективных плоскостей малых размерностей. Данная программа выводит на экран матрицу инцидентности соответствующей плоскости указанного пользователем порядка. Программный продукт может быть использован в качестве учебного пособия при изучении таких важных комбинаторных объектов, как уравновешенные неполные блок-
8
схемы, частным случаем которых являются аффинные и проективные плоскости.
Сделаем несколько замечаний технического характера. Основная информация о понятиях и обозначениях, систематически используемых в диссертации, дается в разделе "Основные понятия". Нумерация теорем, лемм и следствий в диссертации сквозная с учетом номера главы, нумерация формул и рисунков сквозная. Например, ссылка "теорема 2.11 "означает теорему 2.11 из главы 2.
Основные результаты диссертационного исследования докладывались и обсуждались на Международной алгебраической конференции, посвященной 100-лстию со дня рождения Куропга А.Г.(г. Москва, МГУ, 2008 г.), XV Международной конференции "Проблемы теоретической кибернетики"(г. Казань, КГУ, 2008 г.), XXI Международной научной конференции "Математические методы в технике и технологиях ММТТ-21"(г. Саратов, СГТУ, 2008 г.), Международной научной конференции, посвященной 100-лстию со дня рождения профессора Вагнера В.В.(г. Саратов, СГУ, 2008 г.), Международной конференции "Мальцевские чтения", посвященной 100-летию со дня рождения Мальцева А.И.(г. Новосибирск, НГУ, 2009 г.), Международной алгебраической конференции, посвященной 80-летию со дня рождения Кострикина А.И.(г. Нальчик, КБГУ, 2009 г.), Международной научной конференции "Компьютерные науки и информационные технологии "(г. Саратов, СГУ, 2009 г.), Международной конференции "Воображаемая логика"Васильева H.A. и современные неклассические логики"(г. Казань, КФУ, 2010 г.), ежегодных научных конференциях механико-математического факультета "Актуальные проблемы математики и механики"(г. Саратов, СГУ, 2008, 2009. 2010 гг.), ежегодных конференциях по итогам научно-исследовательской работы Саратовского государственного социально-экономического университета "Социально-экономическое развитие России: Проблемы, поиски,
решения"(Саратов, СГСЭУ, 2008, 2009, 2010 гг.).
9
1 Основные понятия
В работе используется общепринятая терминология и известные определения из универсальной алгебры [16J, [21], алгебры отношений [5], теории полугрупп [15], [20], теории гиперграфов [12] и алгебраической теории автоматов [25]. В этой главе приводятся основные понятия, необходимые для поел еду ющего изложения результатов диссертации.
1.1 Элементы алгебры отношений, теории полугрупп и теории гиперграфов
Декартовым (или прямым) произведением двух множеств А, В называется множество А х В, которое состоит из всех упорядоченных пар (а, Ь) элементов a £ А, b £ В. В частности, если множества А, В равны, то прямое произведение Ах В называется декартовым квадратом множества А и обозначается символом А2.
Подмножества декартова произведения А х В множеств /1 и В называются бинарными отношениями между элементами множеств А, В и обозначаются строчными греческими буквами (возможно с индексами): /з.сг, pi, Р2—
Для бинарного отношения р С А х В область определения dom р и множество значений im р определяются как подмножества соответствующих множеств /1 и В по следующим формулам:
domр = {а : (а, Ь) £ р для некоторого Ь £ В} imр = {6 : (а, Ь) € р для некоторого а G А).
Для любого подмножества X С А множество
р(Х) = {Ь € В : (х, Ь) £ р для некоторого гг € X}
называется образом множества X относительно отношения р. Образ одноэлементного множества X = {а} относительно отношения р
обозначается символом р{а) и называется также срезом отношения р через элемент о..
Бинарное отношение р С А х В называется:
10
- всюду определенным, если dom р — А\
- однозначным (или функцией), если для каждого элемента а € dom р условие (а, Ь) е р выполняется точно для одного элемента 6 6 Б, называемого значением функции р для элемента а и обозначаемого р(а);
- взаимно однозначным, если оно однозначно и для каждого элемент Ъ £ imp условие (а, Ь) е р выполняется точно для одного элемент а 6 А, называемого прообразом функции р для элемента 6 и обозначаемого р~1(Ь).
Обратным для бинарного отношения р С А х В называется бинарное отношение р~1 С В х А, определяющееся по формуле:
Р~1 = {(М) : (а,Ь) G уо}.
Композицией бинарных отношений рС Лх5иа С ßxC называется бинарное отношение ра С Ах С, определяющееся по формуле:
ра = {(а, с) : (а, 6) € д, (6, с) € а для некоторого 6 6 Б}.
Всюду определенное однозначное бинарное отношение (р С А х В называется отображением множества А в множество В и обозначается символом <р : А —* В.
Отображение (р: А —> В называется:
- отображением множества А на множество В (или сюръекцией), если его множество значений im«/? = В\
- взаимно однозначным отображением множества А в множество В (или инъекцией), если оно является взаимно однозначным бинарным отношением;
- взаимно однозначным отображением множества А на множество В (или биекцией), если оно является взаимно однозначным отображением А на В;
- преобразованием множества А, если А = В]
11
- Київ+380960830922