Алгебраическая теория универсальных упорядоченных автоматов

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

1 Основные понятия

1.1 Элементы алгебры отношений и теории упорядоченных множеств

1.2 Основы теории универсальных упорядоченных автоматов

1.3 Введение в теорию многоосновных алгебраических систем

2 Универсальные упорядоченные полуавтоматы

2.1 Конкретная характеризация универсальных упорядоченных полуавтоматов

2.2 Абстрактная характеризация универсальных упорядоченных полуавтоматов

2.3 Относительно элементарная определимость универсальных упорядоченных полуавтоматов в классе полугрупп
2.4 Взаимосвязь свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов

3 Универсальные упорядоченные автоматы

3.1 Об определяемости универсальных упорядоченных автоматов полугруппами входных сигналов
3.2 Изоморфизмы универсальных упорядоченных автоматов
3.3 Группы автоморфизмов универсальных упорядоченных автоматов
3.4 Конкретная характеризация универсальных упорядоченных автоматов
Список литературы

Работа посвящена развитию алгебраической теории универсальных упорядоченных автоматов. Теория автоматов представляет собой один из основных разделов математической кибернетики, главными объектами изучения которой являются устройства, предназначенные для преобразования информации. Такие устройства естественным образом возникают в многочисленных задачах, связанных с вычислительной техникой и управлением, в задачах информационно-коммуникационных технологий, экономической логистики и многих других. В общем случае устройство преобразования может находиться в различных состояниях, которые изменяются под влиянием определенных внешних воздействий (входных сигналов) и, в свою очередь, сами воздействуют на внешнюю среду (с помощью выходных сигналов). Математической моделью такого устройства является трехосновная алгебраическая система, называемая автоматом и представляющая собой алгебру А = (X, Б, У, 8, А) с тремя основными множествами X, Б, У и двумя бинарными операциями 5 : X х £ —> X, X : X х Б —> У. При этом X называется
множеством состояний автомата, Б - множеством входных сигналов, У - множеством выходных сигналов. Операция 8 - это функция от двух переменных X € X, й в Б со значениями 8(х, 5) в множестве состояний X. Она называется функцией переходов автомата и показывает, как входной сигнал в преобразует состояние х в новое состояние х' = 8(х, в). Операция Л - это функция от тех же переменных х 6 X, з € Б, но со значениями Х(х, в) в множестве выходных сигналов У. Она называется выходной функцией автомата А и указывает значение сигнала на выходе у = А (я, з) в зависимости от состояния автоматах и значения входного сигнала 5.
В зависимости от специфики рассматриваемых задач математической кибернетики, устройство преобразования информации может моделироваться автоматом, у которого множество состояний
и множество выходных сигналов наделены дополнительной математической структурой (например, структурой линейного
пространства, упорядоченного множества, топологического пространства и другими), которая сохраняется функциями переходов

и выходными функциями этого автомата (см., например, известные работы В.М.Глушкова [9] и Б.И.Плоткина [20]). Так, известные конкретные задачи математической кибернетики приводят к понятиям линейных, упорядоченных, топологических, вероятностных и нечетких автоматов. Исследованиям таких автоматов посвящены, например, работы Скорнякова Л.А., Сперанского Д.В., Сытника A.A., Плоткина Б.И. и Филькенштейна М.Я., Гечега Ф., Каца М.М. и многих других. В общем случае автоматы, основные множества которых наделены дополнительной алгебраической структурой, называются структуризованными автоматами. Многочисленные исследования в этом направлении характеризуются широким использованием алгебраических средств, и, таким образом, автомат - один из основных объектов математической кибернетики - становится предметом научного интереса алгебраической теории автоматов, которая непосредственно связана с важными разделами универсальной алгебры [13] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, связанным с их поведением, анализом и синтезом, к теории языков и алгоритмов и ко многим другим разделам математической кибернетики.
В настоящей работе продолжается исследование этого направления: здесь изучаются алгебраические свойства упорядоченных автоматов, т.е. автоматов, у которых множество состояний и множество выходных сигналов наделены алгебраической структурой упорядоченного множества, которая сохраняется функциями переходов и выходными функциями этого автомата.
Основное внимание в настоящей работе уделяется так называемым универсальным упорядоченным автоматам, подавтоматы которых охватывают гомоморфные образы всех рассматриваемых упорядоченных автоматов. Например, при изучении упорядоченных полугрупповых автоматов без выходных сигналов (называемых также полуавтоматами [1]) таким универсальным упорядоченным автоматом является полуавтомат Atm(Ar) = (А, End А, 5) с упорядоченным множеством состояний X = (X, <), полугруппой входных сигналов End А (состоящей из эндоморфизмов упорядоченного множества А) и функцией переходов ö(x,ip) = ip(x) (здесь х € A, ip 6 End А), поскольку для

3) в полугруппе S входных сигналов полуавтомата А найдутся такие элементы Хо,уо, что формула Р(хо,Уо',х,у) задает отношение порядка < на множестве X, для которого упорядоченный полуавтомат А = (X,S,S) изоморфен
универсальному упорядоченному полуавтомату А = Atm(X);
5) для любой формулы Ф языка элементарной теории упорядоченных полуавтоматов эффективно строится такая формула Ф языка элементарной теории полугрупп, что если Ф истинна на универсальном упорядоченном полуавтомате А, то формула Ф истинна на его полугруппе входных сигналов 1пр(А) и, с другой стороны, если Ф истинна на полугруппе 1пр(А), то на универсальном упорядоченном полуавтомате А истинна формула Ф или двойственная ей формула Ф.
Доказательство. Пусть А = (X, S, 6) - некоторый универсальный упорядоченный полуавтомат с нетривиально упорядоченным множеством СОСТОЯНИЙ X = (X, <х) и полугруппой входных
сигналов S = EndX. Так как полугруппа S содержит все постоянные преобразования множества X, то в силу леммы 2.7 для определенной выше формулы М{х) выполняется утверждение 1).
Напомним, что построенная в разделе 2.2 биекция / множества X на множество X всех постоянных преобразований из S отображает введенное в разделе 2.1 каноническое отношение Q С X2 полугруппы S в отношение Q С S2, которое определяется по формуле:
Q = {(х,у) 6 S2 : q(x, у)},

q(x, у) = (МО) Л М(у) Л (V и, и,ифи)(М(и) Л M(v) ==t> (П (и, v, х, у) V П (v,u;x,y)))).
Рассмотрим следующую формулу языка элементарной теории полугрупп:
D{x,y,z) = (М(х) Л M(z) A (3y)(xy = z)).