Логико-алгебраические методы теории гиперграфических автоматов

• Автор: Хворостухина, Екатерина Владимировна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Саратов
• Количество страниц: 132 с.

Содержание
Введение
1 Основные понятия
1.1 Элементы алгебры отношений, теории полугрупп и теории гииерграфов
1.2 Гинерграфические автоматы
1.3 Обратимые входные сигналы универсальных гииерграфических автоматов
2 Универсальные гиперграфические автоматы
2.1 Определяемость гииерграфических автоматов полугруппами их входных сигналов
2.2 Конкретная характеризация универсальных гииерграфических автоматов
2.3 Абстрактная характеризация универсальных гииерграфических
автоматов
3 Взаимосвязь свойств автоматов и их полугрупп входных сигналов
3.1 Относительно элементарная определимость универсальных
гииерграфических автоматов в классе полугрупп
3.2 Элементарная эквивалентность универсальных гииерграфических автоматов
3.3 Проблемы разрешимости элементарных теорий универсальных гииерграфических автоматов
3.4 Гомоморфизмы универсальных гиперграфичееких автоматов
3.5 Мономорфизмы универсальных гииерграфических автоматов
Заключение

Введение
Работа посвящена развитию алгебраической теории универсальных гинерграфичсских автоматов. Теория автоматов представляет собой один из основных разделов математической кибернетики, главными объектами изучения которой являются устройства, предназначенные для управления динамическими системами, изменяющими свои состояния под воздействием сигналов из внешней среды. Примерами таких устройств могут служить электронно-вычислительное, телекоммуникационное оборудование. бытовая техника и т.п. Математической моделью таких устройств является автомат А = (Х,Я,ё), который представляет собой двухосновную алгебраическую систему с двумя основными множествами X, 5 и бинарной операцией 5 : X х 3 —> X. При этом X называется
множеством состояний, 5 множеством входных сигналов, 5 функцией пререходов автомата. Отображение 8 для каждого фиксированного в € 51 определяет соответствующее этому входному сигналу 5 преобразование ф,. множества состояний, которое для каждого х € X указывает состояние 8а{х) — 8(х, з), в которое переходит автомат А при входном сигнале в. Последовательное действие входных сигналов 5,4 6 Я реализуется композицией преобразований 83, ф. В результате множество 5 можно рассматривать как полугруппу с ассоциативной бинарной операцией •, которая взаимосвязана с функцией переходов автомата но формуле: 8(х, 5 ■ 4) = 8(8(х, а), 4) для любых жеХи«,4 65.
В зависимости от специфики рассматриваемых задач математической кибернетики, устройства управления динамическими системами могут моделироваться структуризованными автоматами, у которых множества состояний наделены дополнительной математической структурой, сохраняющейся функциями переходов таких автоматов. В качестве таких дополнительных структур могут выступать, например, структуры вероятностного пространства, линейного пространства, топологического пространства, упорядоченного множества и другие. Автоматы, наделенные такими дополнительными структурами, называются [25], соответственно, вероятностными автоматами, линейными автоматами,

топологическими автоматами, упорядоченными автоматами. Исследованиям таких автоматов посвящены известные работы Аблаева Ф.М., Бухараева Р.Г., Скорнякова Л.А., Сперанского Д.В., Плоткина Б.И., Ф. Гечега, Акимовой С.А. и многих других. При таком подходе структуризоваиные автоматы являются объектами исследования алгебраической теории автоматов, которая основывается на фундаментальных понятиях универсальной алгебры [16] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, связанным с их поведением, анализом и синтезом, к теории формальных языков и к другим разделам математической кибернетики [25], [35].
В настоящей работе продолжается исследование структуризованных автоматов: здесь рассматриваются так называемые гиперграфические автоматы, т.е. автоматы, у которых множества состояний наделены дополнительной алгебраической структурой гиперграфа [12]. Поскольку гииерграфы являются естественным обобщением понятий обыкновенного графа, плоскости [14], [31] и разбиения множества, то изучаемые автоматы образуют достаточно широкий и весьма важный класс автоматов, многообразие которых охватывает, в частности, автоматы, у которых множества состояний являются плоскостями (например, проективными или аффинными), а также автоматы, у которых множества состояний разбиваются на классы некоторой эквивалентности. В работе рассматриваются полугрунновые автоматы, поэтому далее под гииерграфическим автоматом будем понимать нолугрунновой автомат А — (X,S,S), у которого множество состояний X наделено такой структурой гииерграфа Н = (X, L), что при любом
входном сигнале s € S функция переходов 8S : X --------> X является
эндоморфизмом гиперграфа Н. Основное внимание в работе уделяется гииерграфическим автоматам, у которых множества состояний являются гииерграфами особого вида - эффективными гиперграфами с р—определимыми ребрами. В частности, эффективные гиперграфы с 1-определимыми ребрами - это гииерграфы, ребра которых образуют нетривиальное разбиение множества вершин без одноэлементных классов. Кроме того, эффективными гииерграфами с 2-оирсделимыми ребрами являются конечные плоскости - специальные комбинаторные

Результат применения преобразования а к проективной плоскости представлен на рисунке 8.
Рис. 8: Результат применения преобразования а
В силу вышесказанного преобразование а является автоморфизмом проективной плоскости П13. Покажем, что а действительно сохраняет коллинеарность соответствующих точек.
Из рисунка видно, что преобразование а сохраняет коллинеарность соответствующих точек, при этом имеем
а(Я) = а{А, В, С, М} = (а(Л), а(Я), а(С),а(М)} = {£>, Я, С, 7} = 17,
а(Я) — 1,
а(к) = а{ Д Е, Я, М} = (а(£>), а(Е), а(Я), а(М)} = {А, Е, I, .7} - 18,
а{к) = Я,
а(13) = а{С, Я, /, М} - {&((?), а(Я), а(7), а(М)} - {С, В, Я, .7} = /9)
а(Я) =
а(1п) = а{Л, Я, Я, Я} = (а(И), й(Я), а(Я), а(К)} = {Я, 7, В, К} = /12,
а(Яі) = ^
Прямые І4,І5,к,Ііа преобразование а оставляет на месте, то есть
^(Я) ~ Я? ^(Я) 1= Я> ^(Я) = Я? а(/ю) Ясь а(Яз) Яз-