Содержание к диссертации
Введение
1 Основные понятия 11
1.1 Элементы алгебры отношений и теории упорядоченных множеств 11
1.2 Основы теории универсальных упорядоченных автоматов 17
1.3 Введение в теорию многоосновных алгебраических систем 20
2 Универсальные упорядоченные полуавтоматы 28
2.1 Конкретная характеризация универсальных упорядоченных полуавтоматов 28
2.2 Абстрактная характеризация универсальных упорядоченных полуавтоматов 39
2.3 Относительно элементарная определимость универсальных упорядоченных полуавтоматов в классе полугрупп 44
2.4 Взаимосвязь свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов 55
3 Универсальные упорядоченные автоматы 65
3.1 Об определяемости универсальных упорядоченных автоматов полугруппами входных сигналов 65
3.2 Изоморфизмы универсальных упорядоченных автоматов 71
3.3 Группы автоморфизмов универсальных упорядоченных автоматов 78
3.4. Конкретная характеризация универсальных упорядоченных автоматов 83
Список литературы 95
- Основы теории универсальных упорядоченных автоматов
- Абстрактная характеризация универсальных упорядоченных полуавтоматов
- Взаимосвязь свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов
- Об определяемости универсальных упорядоченных автоматов полугруппами входных сигналов
Введение к работе
Работа посвящена развитию алгебраической теории универсальных упорядоченных автоматов. Теория автоматов представляет собой один из основных разделов математической кибернетики, главными объектами изучения которой являются устройства, предназначенные для преобразования информации. Такие устройства естественным образом возникают в многочисленных задачах, связанных с вычислительной техникой и управлением, в задачах информационно-коммуникационных технологий, экономической логистики и многих других. В общем случае устройство преобразования может находиться в различных состояниях, которые изменяются под влиянием определенных внешних воздействий (входных сигналов) и, в свою очередь, сами воздействуют на внешнюю среду (с помощью выходных сигналов). Математической моделью такого устройства является трехосновная алгебраическая система, называемая автоматом и представляющая собой алгебру А = (X. S. У. 6. А) с тремя основными множествами X, S, Y и двумя бинарными операциями 8 : X х S —> X, \ : X х S —> У. При этом X называется множеством состояний автомата, S - множеством входных сигналов, Y - множеством выходных сигналов. Операция 6 - это функция от двух переменных х Є Xt s Є S со значениями 5(х, s) в множестве состояний X. Она называется функцией переходов автомата и показывает, как входной сигнал s преобразует состояние х в новое состояние х' — 5(х, s). Операция Л - это функция от тех же переменных х Є X. s Є S, но со значениями A(.x,s) в множестве выходных сигналов У. Она называется выходной функцией автомата Л и указывает значение сигнала на выходе у = Х(х. s) в зависимости от состояния автомата х и значения входного сигнала s.
В зависимости от специфики рассматриваемых задач математической кибернетики, устройство преобразования информации может моделироваться автоматом, у которого множество состояний и множество выходных сигналов наделены дополнительной математической структурой (например, структурой линейного пространства, упорядоченного множества, топологического пространства и другими), которая сохраняется функциями переходов
и выходными функциями этого автомата (см., например, известные работы В.М.Глугакова [9] и Б.И.Плоткина [20]). Так. известные конкретные задачи математической кибернетики приводят к понятиям линейных, упорядоченных, топологических, вероятностных и нечетких автоматов. Исследованиям таких автоматов посвящены, например, работы Скорнякова Л.А., Сперанского Д.В., Сытника А.А., Плоткина Б.И. и Филькенштейна М.Я., Гечега Ф., Каца М.М. и многих других. В общем случае автоматы, основные множества которых наделены дополнитапьной алгебраической структурой, называются структуризованными автоматами. Многочисленные исследования в этом направлении характеризуются широким использованием алгебраических средств, и, таким образом, автомат - один из основных объектов математической кибернетики - становится предметом научного интереса алгебраической теории автоматов, которая непосредственно связана с важными разделами универсальной алгебры [13] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, связанным с их поведением, анализом и синтезом, к теории языков и алгоритмов и ко многим другим разделам математической кибернетики.
В настоящей работе продолжается исследование этого направления: здесь изучаются алгебраические свойства упорядоченных автоматов, т.е. автоматов, у которых множество состояний и множество выходных сигналов наделены алгебраической структурой упорядоченного множества, которая сохраняется функциями переходов и выходными функциями этого автомата.
Основное внимание в настоящей работе уделяется так называемым универсальным упорядоченным автоматам, подавтоматы которых охватывают гомоморфные образы всех рассматриваемых упорядоченных автоматов. Например, при изучении упорядоченных полугрупповых автоматов без выходных сигналов (называемых также полуавтоматами [1]) таким универсальным упорядоченным автоматом является полуавтомат Atmpf) = (X, EndX.,6) с упорядоченным множеством состояний X — (X, <)- полугруппой входных сигналов End X (состоящей из эндоморфизмов упорядоченного множества^) и функцией переходов 5(х,<р) = tp(x) (здесь х Є X, ц> Є End X). поскольку для
любого упорядоченного полугруппового полуавтомата А = (X, S, 6) с упорядоченным множеством состояний X существует единственный гомоморфизм А в Atm(X). В таком контексте полугруппа End X эндоморфизмов упорядоченного множества X играет определяющую роль для автоматов А с упорядоченным множеством состояний X. Поэтому алгебраическая теория универсальных упорядоченных автоматов имеет непосредственное отношение к одному из основных разделов современной алгебры - обобщенной теории Галуа, начало которой было положено в исследованиях Э.Галуа и которая посвящается изучению математических объектов путем исследования некоторых производных алгебр отображений, специальным образом связанных с исходными объектами. В нашем примере изучаемым математическим объектом является универсальный упорядоченный полуавтомат Atm(X) и производной алгеброй отображений - его полугруппа входных сигналов EndX. Следовательно, алгебраическая теория упорядоченных автоматов тесным образом связана с общеизвестной задачей определяемое математических объектов их эндоморфизмами и автоморфизмами, которая сформулирована в числе прочих актуальных математических проблем в известной книге С. Улама [23].
Проведенные в работе исследования универсальных упорядоченных автоматов следуют уже сложившемуся традиционному кругу вопросов обобщенной теории Галуа: принципиальное значение имеет задача о том, как производная алгебра отображений определяет исходный объект; затем исследуется, какими абстрактными свойствами характеризуется такая производная алгебра отображений: наконец, с помощью полученных результатов изучаются взаимосвязи свойств исходного объекта и его производной алгебры отображений. Такие вопросы для групп автоморфизмов алгебраических систем, полугрупп эндоморфизмов графов, колец линейных преобразований векторных пространств и других алгебр преобразований весьма успешно решались Б.И.Плоткиным [21], Л.М.Глускиным [7], Ю.М.Важениным [3] и другими авторами. Особое внимание в этом направлении уделялось изучению групп автоморфизмов и полугрупп эндоморфизмов графов: в работе [25] Р.Фрухт доказал, что для любой конечной абстрактной
группы существует граф, группа автоморфизмов которого изоморфна данной группе, и в работе [26] З.Хедрлин и А.Пультр доказали, что для любой конечной абстрактной полугруппы с единицей существует граф, полугруппа эндоморфизмов которого изоморфна данной полугруппе. Эти результаты дают абстрактную характер изацию групп автоморфизмов и полугрупп автоморфизмов графов и имеют непосредственное отношение к поставленному Д.Кенигом в [28] вопросу: каким условиям должна удовлетворять группа подстановок из п элементов, чтобы существовал п-вершинный граф, группа автоморфизмов которого совпадает с этой группой подстановок? В более общей форме эта задача формулируется В.Г.Визингом [5] следующим образом: дана группа подстановок: найти все графы, для которых данная группа является группой автоморфизмов. Эта известная и до сих пор не решенная задача является частным случаем сложной проблемы конкретной характеризации [27] производных алгебр отображений в обобщенной теории Галуа, т.е. проблемы описания таких условий, при которых алгебра отображений равна производной алгебре отображений изучаемого математического объекта. В этом направлении отдельные продвижения были сделаны М.Краснером [29], Е.С.Ляпиным [16]. Б.Йонсоном [27], Д.Бредихиным [2] и другими авторами для полугрупп эндоморфизмов релятивов, групп автоморфизмов и инверсных полугрупп частичных автоморфизмов универсальных алгебр. К этому же направлению относится задача упорядочиваемости полуавтоматов, исследованная М.М.Кацем [12].
Принципиальным отличием проведенных в диссертации исследований является положенное в их основу решение задачи конкретной характеризации универсальных упорядоченных автоматов. Для изучаемых в начале работы универсальных упорядоченных полуавтоматов такая задача формулируется следующим образом:
при каких условиях полуавтомат А с множеством состояний X и полугруппой входных сигналов S, рассматриваемой как полугруппа преобразований множества X, является универсально упорядочиваемым полуавтоматом, т.е. на множестве состояний автомата А можно так определить нетривиальное отношение порядка <, что полугруппа
эндоморфизмов EndX упорядоченного множествах — (X, <) совпадет с полугруппой входных сигналов автомата Л?
Главным инструментом решения сформулированной задачи является разработанная в диссертации техника канонических отношений полугрупп преобразований, которые определяются в исходных полугруппах формулами языка узкого исчисления предикатов (УИП). Такое решение поставленной задачи дает эффективный метод последовательного изучения взаимосвязи свойств универсальных упорядоченных полуавтоматов и их полугрупп входных сигналов.
В работе изучаются также универсальные упорядоченные автоматы, подавтоматы которых охватывают гомоморфные образы всех упорядоченных полугрупповых автоматов с выходными сигналами. Такие универсальные упорядоченные автоматы являются структуризованными автоматами Atm(X, У) — (X, S, У. ё, А) с упорядоченным множеством состояний X = (X, <х), упорядоченным множеством выходных сигналов У = (У, <у), полугруппой входных сигналов S — EnclX х Hom(X Y) (состоящей из пар s = (<р, ф) эндоморфизмов ip упорядоченного множества X и гомоморфизмов ф упорядоченного множества^ в упорядоченное множество У), функцией переходов 5(%.s) — ip(x) и выходной функцией X(x,s) = ф(х) (здесь х Є X и s = {ір,ф) - элемент полугруппы S = EndX х Hom(X,Y)).
Для таких универсальных упорядоченных автоматов в первую очередь исследован вопрос о том, как универсальные упорядоченные автоматы определяются своими полугруппами входных сигналов?
В результате решения этой задачи в работе также описаны строения изоморфизмов универсальных упорядоченных автоматов и групп их автоморфизмов.
Особое внимание в работе уделено исследованию проблемы конкретной характеризации универсальных упорядоченных автоматов, которая формулируется следующим образом;
при каких условиях автомат А = (X. 5. У", 6, А) с множеством состояний X. множеством выходных сигналов У и полугруппой входных сигналов S является универсально упорядочиваемым автоматом?
Идея решения задачи заключается в том, что по полугруппе входных
сигналов автомата Л на его множествах X, Y строятся канонические отношения и с их помощью формулируются необходимые и достаточные условия, при которых на этих множествах X, У существуют такие отношения порядков, что полугруппа S совпадает с полугруппой Епс1ХхНот(Х,У).
В первой главе работы излагаются основные алгебраические понятия, необходимые для последовательного развития алгебраической теории упорядоченных автоматов. Здесь уточняется общепринятая терминология и приводятся необходимые определения и обозначения из алгебры отношений, теории упорядоченных множеств, теории автоматов и теории многоосновных алгебр.
Во второй главе диссертации рассматриваются универсальные упорядоченные полуавтоматы. Центральный результат этой главы дает решение задачи конкретной характеризации таких автоматов. Главным инструментом решения сформулированной задачи является разработанная в диссертации техника канонических отношений полугрупп преобразований.
В разделе 2.2 получена абстрактная характеристика универсальных упорядоченных полуавтоматов, которая дает необходимые и достаточные условия, при которых абстрактный полуавтомат А изоморфен некоторому универсальному упорядочиваемому полуавтомату.
В разделе 2.3 с помощью полученной в теореме 2.6 конкретной характеристики универсальных упорядоченных полуавтоматов доказана относительно элементарная определимость [10] класса таких полуавтоматов в классе всех полугрупп с целью дальнейшего изучения взаимосвязи абстрактных и элементарных свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов.
В разделе 2.4 с помощью относительно элементарной определимости класса универсальных упорядоченных полуавтоматов в классе полугрупп исследованы задачи о взаимосвязи свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов, которые непосредственно связаны с известными результатами Л.М.Глускина [б] и Ю.М.Важенина [3].
В третьей главе диссертации приводятся результаты последовательного изучения универсальных упорядоченных автоматов. В разделе 3.1 исследован вопрос о том, как универсальный упорядоченный автомат определяется своей полугруппой входных сигналов. Полученный результат обобщает известный результат Глускина Л.М. [6] об определяемое упорядоченных множеств полугруппами их эндоморфизмов.
В разделе 3.2 изучается взаимосвязь изоморфизмов универсальных упорядоченных автоматов с изоморфизмами их полугрупп входных сигналов и изоморфизмами их упорядоченных множеств состояний и упорядоченных множеств выходных сигналов.
В разделе 3.3 описывается строение групп автоморфизмов универсальных упорядоченных автоматов.
В разделе 3.4 приводится центральный результат третьей главы, который дает решение задачи конкретной характеризации универсальных упорядоченных автоматов.
Полученные результаты решают ряд принципиальных вопросов о взаимосвязи упорядоченных автоматов с их полугруппами входных сигналов, а также дают весьма эффективный инструмент для дальнейшего разностороннего исследования этой проблематики в алгебраической теории автоматов и для разнообразных приложений к комбинаторному исследованию автоматов, к изучению вопросов классификации автоматов средствами языка УИП и к анализу проблем разрешимости элементарных теорий классов автоматов.
Сделаем несколько замечаний технического характера. Справка об основных понятиях и обозначениях, систематически используемых в диссертации, дается в разделе "Основные понятия". Более специальные определения приводятся в начале каждой главы. Нумерация теорем, лемм и следствий в диссертации сквозная с учетом номера главы, нумерация формул своя в каждой главе. Например, ссылка "теорема 2.6"означает теорему 2.6 из главы 2. Окончание доказательства обозначается символом П.
Результаты диссертации докладывались на секции "Алгебраические аспекты теории управляющих систем" научных конференций
механико-математического факулвтета Саратовского государственного университета (2003, 2004, 2005, 2006), на секции "Проблемы теоретической кибернетики" научной конференции Саратовского государственного социалвно-экономического университета (2005), на объединенном семинаре Саратовского государственного университета по дискретной математике и математической кибернетике (2006).
Основы теории универсальных упорядоченных автоматов
В настоящей работе под автоматом понимается алгебраическая система А = (X, S, У, 5, А) с тремя основными множествами X, 5, У и двумя бинарными операциями.
Здесь X называется множеством состояний автомата, 3 - множеством входных сигналов и У - множеством выходных сигналов. Операция S -это функция от двух переменных х Є X, s Є S со значениями 5(х, $) в множестве состояний X. Она называется функцией переходов автомата и показывает, как входной сигнал $ преобразует состояние х в новое состояние х1 = ё(х, s). Операция Л - это функция от тех же переменных х Є X, з Є 5, но со значениями А(х\ s) в множестве выходных сигналов Y. Она называется выходной функцией автомата А и указывает значение сигнала на выходе у = А (ж, s) в зависимости от состояния автомата х и значения входного сигнала s.
Автомат обозначается следующим образом: А — (X, S, У, 5, X) или более кратко А = (Х: S,У). Автомат А = (X, S, У) называется полугрупповым, если на множестве его входов S определена ассоциативная бинарная операция , которая взаимосвязана с операциями 5 и А следующими аксиомами. Полугруппу входных сигналов автомата будем обозначать также 1пр(А). Заметим, что при фиксированном значении s Є S получаем отображения 6s(x) — 5(х, s) (х Є X) множества X в X и Xs(x) = Л(ж, s) (ж Є X) множества X в У, которые называются также функцией перехода и выходной функцией, определенными входным сигналом s. Автомат A = (X,S,Y) называется точным автоматом, если у него нет равнодействующих входных сигналов. Это означает, что для любых s. t S,s ф t выполняется (5,4,XS) Ф (8t,Xt). т.е. по крайней мере одно из отображений 5Ь1 Аь. отлично от соответствующего отображения 5t, А;. В этом случае действие входного сигнала s Є S полностью определяется действием пары отображений (6S,XS) и можно отождествить входной сигнал s с парой таких отображений (6S, As). Следуя Б.И. Плоткииу [20], автоматы, множество состояний и множество выходных сигналов которых не наделены дополнительной структурой, называются чистыми. Автоматы, множество состояний и множество выходных сигналов которых наделены дополнительной структурой, согласованной с операциями автомата, называются структуризованными. В частности, если множество состояний и множество выходных сигналов автомата наделены дополнительной структурой отношения порядка, согласованной с операциями автомата, то такой автомат называется также упорядоченным автоматом. Таким образом, далее под упорядоченным автоматом будем понимать упорядоченный полугрупповой автомат, т.е., следуя [20], алгебраическую систему вида А — (X,SfY,6,X), где X {Х, х) - упорядоченное множество состояний автомата, S = (5, ) - полугруппа входных сигналов, Y — (У, у) - упорядоченное множество выходных сигналов, 8 : X х S —X - функция переходов и. X : X х S — У- выходная функция, удовлетворяющие при всех х,у X, s,s Є S, условиям: 8(х, s s ) — 6(S(x, s), s ), X(x,s s ) — X(6(x,s),s )) и при каждом фиксированном значении s отображение Ss(x) = 8(х, s) (х Є X) является эндоморфизмом упорядоченного множества X, отображение Хц(х) — Х(х, s) (х Є X) - гомоморфизмом X в Y. Автомат, множество состояний которого нетривиально упорядочено, будем называть нетривиально упорядоченным автоматом. Классификацию упорядоченных множеств распространяем на классификацию автоматов и полуавтоматов. Например, автомат будем называть линейно упорядоченным, если линейно упорядочены его множество состояний и множество выходных сигналов. Универсальным упорядоченным автоматом называется автомат Atm(X, Y) — (X, 5, У, (5, Л) с упорядоченным множеством состояний X = (X, x)i упорядоченным множеством выходных сигналов Y — (Y, Y), полугруппой входных сигналов S = End A х Hom(X, Y) (состоящей из нар $ = (tp, ф) эндоморфизмов ip упорядоченного множества X и гомоморфизмов ф упорядоченного множества X в упорядоченное множество Y). функцией переходов 6(x,s) — р(х) и выходной функцией Л(х, s) — ф(х) (здесь х Є X и s — ( р, ф) - элемент полугруппы S — EndX х Нот(А. У)). Автомат А = (X, S, У, 6, А) называется универсально упорядочиваемым, если его можно превратить в универсальный нетривиально упорядоченный автомат Atm(AT, Y) путем задания некоторого нетривиального порядка х на множестве состояний X и некоторого порядка у на множестве выходных сигналов У. Упорядоченный автомат А — (X,S, Y,5, А), у которого упорядоченное множество состояний X и упорядоченное множество выходных сигналов Y являются двойственно упорядоченными по отношению к упорядоченным множествам X. Y соответственно, называется автоматом, двойственно упорядоченным по отношению к автомату А - (X, S1, Y, 6, А). Изоморфизм F упорядоченных автоматов А\ — (А , Si, Уі, i, Ai) и Ач = {X Si Y i i i) определяется как изоморфизм трехосновных алгебраических систем А\ и А упорядоченной тройкой F — (/, тг, д) изоморфизмов соответствующих упорядоченных множеств и полугрупп / : Xi —» А 2, д : Y\ — Y2, її : S\ -» S2, удовлетворяющих при любых значениях х Є Х\, $ Є S\ следующим условиям:
Абстрактная характеризация универсальных упорядоченных полуавтоматов
При рассмотрении универсальных упорядоченных полуавтоматов по аналогии с производными алгебрами отображений на математических объектах в общей теории Галуа (см., например, [27]) естественно возникает задача их абстрактной характеризации, которая в данном случае кратко формулируется следующим образом [8]: найти совокупность некоторых свойств универсального упорядоченного полуавтомата, сохраняющихся при его произвольном изоморфизме, таких, что если какой-либо абстрактный чистый полуавтомат А = (X, S. 6) обладает всеми свойствами совокупности Г, то полуавтомат А изоморфен универсальному упорядоченному полуавтомату Atmpf ) = (A , End А , 5 ) для некоторого упорядоченного множества Xі — (X , ).
Это означает, что найдется такая пара F — (/, д) биекций / : X —» X , д ; S — End А77, которая согласована с умножением входных сигналов и функцией переходов этих полуавтоматов, т.е. для любых s,t Є S, х Є X выполняются условия:
Такого рода проблемы для ряда полугрупп преобразований исследовались в работах Е.С. Ляпина [15], А.И. Мальцева [18], Л.М. Глускина [8]. В последней работе было введено понятие плотно-вложенного идеала и с его помощью получена абстрактная характеристика полугруппы эндоморфизмов упорядоченного множества.
В настоящем разделе приводится решение задачи абстрактной характеризации универсальных упорядоченных полуавтоматов на основе полученного в разделе 2.1 решения задачи конкретной характеризации таких полуавтоматов. Отметим, что найденное решение поставленной задачи не использует сложное понятие плотно-вложенного идеала. Более того, в полученной абстрактной характеристике универсальных упорядоченных полуавтоматов все свойства, за исключением одного, формулируются на языке элементарной теории полугрупп.
Пусть S - полугруппа преобразований множества X, содержащая все постоянные преобразования этого множества.
Введем следующее обозначение: для любого фиксированного а Є X обозначим о постоянное отображение множества X в точку а. Так как полугруппа S содержит все постоянные преобразования множества X, то соответствие а \— а (а, Є X) определяет биекцию множества X на множество X всех постоянных преобразований из S. Эта биекция отображает введенное в разделе 2.1 каноническое отношение Q с X2 полугруппы S в отношение Q С S2. Покажем, что такое отношение Q в полугруппе преобразований S определяется формулой элементарной теории полугрупп. Хорошо известен следующий результат. Лемма 2.7 Пусть S - полугруппа преобразований множества X. содержащая все постоянные преобразования, этого мнооїсества. Тогда одноместный предикат теории полугрупп М(х) — (V у) (ух х) определяет в полугруппе S множество всех ее элементов, являющихся постоянными преобразованиями множествах, т.е. для любого / є S условие М(/) равносильно тому, что / = а для некоторого а Є X. Лемма 2.8 Для полугруппы S преобразований мнооїсества X, содержащей все постоянные преобразования этого множества, и элементов /ь/2,/з)/4 S условие 11(/1,/2:/3,/4) равносильно тому, что fi = ОІ для некоторых а, Є X {1 і 4) и существует преобразование / Є S, для которого /2(оь а2) — (а3, 04). Доказательство. Пусть для элементов /1,/2,/3,/4 S выполняется условие П(/і,/2; /3,/4)- По лемме 2.7 условие M(/j) равносильно условию /і = аї для некоторого а; Є X (1 і 4). По определению предиката П существует преобразование / Є S такое, что a[f = 03,02/ = Щ. С другой стороны, of/ = f(a-[), a f — f (02)- Значит, выполняются равенства /(а2) = а3, /(о2) = а4; т.е. /2(аь а2) = (а3, а4). Пусть выполняется условие fi — а г для некоторых аг Є X и существует преобразование / Є S, для которого {ау.а } = (13,(). По лемме 2.7 условие fi =аї для некоторых а,; 6 X (К г 4) равносильно выполнению условия M(Ji) (1 г 4). Следовательно, справедливо условие П(/ь/25/3,/4)- Определим 2-местный предикат теории полугрупп q(x, у) по формуле: Легко видеть, что на полугруппе преобразований 5 такой предикат q(x,y) определяет описаннное выше бинарное отношение Q по формуле: Теорема 2.9 Произвольный чистый полуавтомат А — (X, S, 5) в том и только том случае изоморфен универсальному нетривиально упорядоченному полуавтомату, если он удовлетворяет следующим условиям:
Доказательство. Рассмотрим универсальный упорядоченный полуавтомат Atm(-X ) для некоторого нетривиально упорядоченного множества X = (Х7 ). Ясно, что полуавтомат Atm(A") удовлетворяет условию (Лі), так как его полугруппа входных сигналов S = EndX содержит все постоянные преобразования множества состояний X и, значит, для любого х Є X однозначно определенное постоянное отображение х : X — {х} при всех у Є X удовлетворяет условию 5{у,х) = х(у) = х. Кроме того, по теореме 2.6 полугруппа входных сигналов S универсального упорядоченного полуавтомата АЬт(Х) Q-замкнута и для канонического отношения Q этой полугруппы выполняются аксиомы (Лі) — (АО- По построению отображение а н а (о I) является биекцией множества X на множество X всех постоянных преобразований из полугруппы эндоморфизмов S. которая отношение Q отображает в отношение Q. Так как на полугруппе S бинарное отношение Q определяется предикатом q(x,y), то полугруппа S удовлетворяет условиям (А{) (Ад). В самом деле, полугруппа S содержит все постоянные преобразования множества X, которые в силу леммы 2.7 являются ее правыми нулями. Тогда выполнимость, например, свойства (А4) для отношения Q равносильна выполнимости для отношения Q следующего свойства:
Взаимосвязь свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов
Доказанная в теореме 2.17 относительно элементарная определимость класса универсальных упорядоченных полуавтоматов в классе полугрупп дает возможность с помощью соответствующего эффективного преобразования формул элементарной теории полуавтоматов в формулы элементарной теории полугрупп получить следующие результаты: 1) исследовать вопрос о том, как универсальные упорядоченные полуавтоматы определяются своими полугруппами входных сигналов; 2) исследовать вопрос об относительной аксиоматизируемости важных классов универсальных упорядоченных полуавтоматов формулами языка элементарной теории полугрупп; 3) проанализировать взаимосвязь различных проблем разрешимости элементарных теорий классов полуавтоматов и элементарных теорий классов полугрупп. Следующий результат показывает, как взаимосвязаны универсальные упорядоченные полуавтоматы с изоморфными полугруппами входных сигналов. Теорема 2.18 Пусть Х\,Х2 - упорядоченные множества,, причем порядок на овном из множеств Xi, Х2 отличен от тождественного. Тогда для универсальных упорядоченных полуавтоматов А\ — Atm(A"i), Л2 = Aimf ) следующие условия эквивалентны: 1) полугруппы, Іпр(Лі), Іпр(Лг) входных сигналов полуавтоматов А\,А% изоморфны, 2) полуавтомат Аі изоморфен полуавтомату А2 или двойственному для него полуавтомату А . Доказательство. Пусть 7Г - изоморфизм полугруппы Іпр(Лі) на полугруппу Іпр(Лг). Предположим, для определенности, что Х\ -нетривиально упорядоченное множество. Зафиксируем элементы а0, &о Є Xi, удовлетворяющие условию ао bG, ао хх &о-Обозначим XQ — ао, г/о — Ъ$ - постоянные отображения множества Х\ в элементы ао и &о, соответственно. Из теоремы 2.17 следует, что 7г(л;о) — со") к(уо) = OIQ - постоянные отображения множества Х2 в некоторые элементы с0, d0 б Х і; удовлетворяющие условию Со ф do и либо со х2 4, либо d0 х2 cQ. По теореме 2.17 в полугруппе Іпр(Лі) с помощью элементов XQ, г/о формулами языка элементарной теории полугрупп L$ определяется полуавтомат Лі, удовлетворяющий условию: Ai = А\. При этом порядок i на множестве состояний Х\ полуавтомата Лі определяется предикатом Р(х(),уо;х,у). Аналогично в полугруппе Іпр(Лг) с помощью элементов 7г(жо), тт(уо) формулами языка элементарной теории полугрупп Lg определяется полуавтомат Л2, удовлетворяющий условию: А% = Л2. При этом порядок 2 на множестве состояний Х2 полуавтомата А 2 определяется предикатом Р(тг(х о),7г(г/о);а;, у). Так как полуавтоматы Лі, Л2 выражаются в соответствующих полугруппах Іпр(Лі), 1пр(Л2) определенными в теореме 2.17 формулами языка элементарной теории полугрупп Lg и изоморфизм 7г сохраняет выполнимость таких формул, то 7Г определяет изоморфизм полуавтомата А\ на полуавтомат Ач или на полуавтомат Аг в зависимости от того, в какие элементы полугруппы Іпр(Лг) отображаются элементы жо,і/о полугруппы Іпр(Лі). Действительно, для любых х,у Є Х\ по определению порядка і условие х і у равносильно выполнимости условия P{XQ, уо; Х, у) в полугруппе Іпр(Лі), что эквивалентно выполнимости условия Р(-к(ха),тг(уо);7г(х),7г(у)) в полугруппе 1пр(Л2). Отсюда следует, что тг(а;) ч тг(у), если TY(XQ) Ч тг(уц) (в случае СО Х2 о), ИЛИ 7г(у) 2 7Г(Ж), ЄСЛИ 7г(ї/0) 2 Ы) (в СЛуЧЭ ( Ха Со) Таким образом, если тг(х о) = CQ. тг(уо) — do и CQ x2do-, то 7Г индуцирует изоморфизм А\ на Л2 и в этом случае с учетом вышеизложенного выполняется свойство А\ = Ач. Если же выполняется условие do x2C(j, то 7г индуцирует изоморфизм А\ на Ач и в этом случае ЛІ Л2. С другой стороны, если полуавтомат Лі изоморфен полуавтомату или Л2, то в силу очевидного равенства \щ){А і) — Іпр(Лг) по определению изоморфизма полуавтоматов выполняется условие Іпр(Лі) Іпр(Л2). П Заметим, что этот результат можно получить также с помощью теоремы Л.М.Глускина [6], Напомним [17], что алгебраические системы А\,Ач фиксированной сигнатуры і\ называются элементарно эквивалентными и записывается А\ = Ач. если выполняется равенство ТЬ(Лі) = Th ), т.е. каждая замкнутая формула УИП сигнатуры fi, истинная на одной из заданных алгебраических П-систем, истинна и на другой. В частности, изоморфные алгебраические П-системы элементарно эквивалентны.
Из основного утверждения теоремы Ю.М.Важенина [3] следует, что для универсальных упорядоченных полуавтоматов А\ — Atm(Xi), Л2 = AtrnfJ ) элементарная эквивалентность полугрупп входных сигналов Іпр(Лі), Іпр(Л2) влечет элементарную эквивалентность упорядоченного множества состояний универсального упорядоченного полуавтомата А\ упорядоченному множеству состояний одного из универсальных упорядоченных полуавтоматов А% Ач. С другой стороны, в работе [3] Ю.М. Важениным построен следующий пример двух элементарно эквивалентных упорядоченных множеств (X, р) и (Xі, р ). у которых полугруппы эндоморфизмов Eud(X) и End(X ) не являются элементарно эквивалентными. Пусть (Xi, pi), (Х2, р2), (X , р\) - изоморфные линейно упорядоченные множества мощности континуум и / - изоморфизм (X\,pi) на {Х%р2). Пусть, далее, [Х2.,р2) линейно упорядоченное множество счетной мощности, элементарно эквивалентное линейно упорядоченному множеству (Xi,p{). Считаем, что Xi П Х2 = 0 и Х[ П Х 2 = 0. Положим X = XY U Х2] X — Х U и на множестве X (соответственно X ) определим отношение порядка (соответственно ) следующим образом: для любых х, у & X (соответственно х .у Є X ) положим х у (соответственно х! у ) тогда и только тогда, когда истинно одно из соотношений (х,у) Є pi, (х,у) Є pi (соответственно (х ,у ) Є Pi, ix ; у ) Рг )- Ю.М. Важениным доказано, что построенные упорядоченные множества элементарно эквивалентны, но полугруппы End(X), End(X ) не являются элементарно эквивалентными.
Приведенный выше пример Ю.М.Важенина показывает, что из элементарной эквивалентности упорядоченных множеств состояний универсальных упорядоченных полуавтоматов в общем случае не следует элементарная эквивалентность полугрупп входных сигналов этих полуавтоматов.
Об определяемости универсальных упорядоченных автоматов полугруппами входных сигналов
Другими словами, гомоморфизм -фГа отображает упорядоченную пару (/(00,/(60)) в упорядоченную пару {да{хо) да{уо))- С другой стороны, так как / - изоморфизм упорядоченного множества Х\ на упорядоченное множество Хч и (ао,6о) Є pi, выполняется условие (/(ао); /()) Є Pi- Тогда, в силу того, что фСа - гомоморфизм упорядоченного множества Х2 на упорядоченное множество Y% выполняется условие (р«(жо). да{уо)) Є $2- Значит, да - изоморфизм Гг на У2. По аналогии ясно, что если / - антиизоморфизм Х\ на Х% то все отображения да(а Є Х{] также будут антиизоморфизмами Y\ на І2 так как в этом случае условие (ао М Є pi влечет (/(йо),/(&о)) Є / и, следовательно, (5о(ї/о) &(яо)) Є $2- Доказательство теоремы 3.2. Очевидно, что в этой теореме условие 3) влечет условие 1). Пусть 7Г - изоморфизм полугруппы S\ входных сигналов автомата Айт(Хі,Уі) на полугруппу S% входных сигналов автомата AtmfXajYa)- Тогда из лемм 3.3-3.6 следует, что этот изоморфизм тг определяется по указанной в лемме 3.6 формуле некоторыми биекциями / : Х\ — Х2, да : У\ Уг (а Є Хі), которые являются изоморфизмами упорядоченных множеств XitYi соответственно на упорядоченные множества , Y2 или на двойственные им упорядоченные множества Х Уг- Значит, условие 1) влечет 2),
С другой стороны, нетрудно проверить, что если упорядоченные множества Х\, Y\ соответственно изоморфны упорядоченным множествам Хг, Уг или упорядоченным множествам Х2, У2, то автомат Atm(Xi,y"i) изоморфен автомату Atm(X2,12) или автомату Atm(X2, У2). Это означает, что условие 2) влечет условие 3).
В настоящем разделе продолжается изучение универсальных упорядоченных автоматов с целью описания строения их изоморфизмов. Как известно [20], изоморфизм F упорядоченных автоматов А, = (Хг, Si, Yh Slt Ai) и A2 = (Z2, S2, П, u, A2) определяется как изоморфизм трехосновных алгебраических систем Лі и А? упорядоченной тройкой F = (/, 7г, #) изоморфизмов соответствующих упорядоченных множеств и полугрупп / : Хі - А , р : Y\ —» Уз тг : i % удовлетворяющих условиям; Ді(я, s)) - й№), Tr(s)), g(Xi{х, s)) = A2(/(x),7r(s)) при любых s Є Si, х Є XL.
Нетрудно убедиться, что в случае А і = Atm(Xi, Yi), А2 = Atm(X2, У2) любой изоморфизм F — (f,ir,g) автомата Ах на автомат А2 полностью определяется изоморфизмами упорядоченных множеств состояний и выходных сигналов таких автоматов, так как в этом случае для любых (ір, ф) є Si выполняется равенство: тт({р,ф) — (f2{tp),{f х д)(ф)). С другой стороны, основной результат работы [6] показывает, что универсальные упорядоченные полуавтоматы определяются своими полугруппами входных сигналов с точностью до двойственности. Взаимосвязь изоморфизмов универсальных упорядоченных автоматов с изоморфизмами их полугрупп входных сигналов и изоморфизмами их упорядоченных множеств состояний и выходных сигналов уточняется также в следующих примерах.
Пример 1. Пусть Z - множество целых чисел с естественным порядком и X — (Х,р) - произвольное упорядоченное множество с компонентами связности Х\,Х-2, ...,ХП:... (здесь и всюду далее в работе под компонентами связности будут пониматься компоненты слабой связности [24] отношения порядка р; т.е. классы эквивалентного замыкания отношения р). Для каждого натурального числап определим отображение дп : Z -+ Z по формуле: дп(х) = х + п (х Є Z). Ясно, что все такие отображения дп являются автоморфизмами упорядоченного множества Z. Рассмотрим универсальный упорядоченный автомат Atm(X, Z) с полугруппой входных сигналов S = EndX х Hom(X, Z) и для каждого элемента { р,ф) Є S положим тт(ір,ф) — ( , ), где ф1р{а) — дп(ф(а)) для любого а Є X, удовлетворяющего условию (р(а) Є Хп. Нетрудно убедиться, что отображение 7Г : S —» S является автоморфизмом полугруппы S, который не может быть компонентой никакого автоморфизма F = (/, -к,д) автомата Atni(X Z).
Пример 2. Пусть В - двухэлементная булева алгебра и Atm(B. В2) универсальный упорядоченный автомат с полугруппой входных сигналов S = EndB х Кот(В,В2). Рассмотрим следующие преобразования ді (і =: 0, 1) упорядоченного множества В2 : да = Д#2 - тождественное преобразование множества В2 и gi(a,b) = (Ь, а) для любых элементов а,Ь В. Очевидно, что отображения да,д\ являются автоморфизмами упорядоченного множества В2. Для каждого элемента ( р,ф) Є S положим -n{ip ) = ((руф ). где ф (а) = ( (а)) для любого а Є В. Тогда, в частности, для тождественного эндоморфизма ір — Дд и постоянного отображения ф множества.
