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

Акимова, Светлана Александровна

Алгебраическая теория универсальных упорядоченных автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Акимова, Светлана Александровна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Саратов МЕСТО ЗАЩИТЫ

2006 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

На правах рукописи

Акимова Светлана Александровна

АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ УНИВЕРСАЛЬНЫХ УПОРЯДОЧЕННЫХ АВТОМАТОВ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

'а*

Саратов - 2006

Работа выполнена на кафедре геометрия Саратовского государственного университета им. Н. Г.Чернышевского

Научный руководитель: доктор физико-математических наук,

профессор Молчанов Владимир Александрович

Официальные оппоненты: доктор физико-математических иаук,

профессор Бредихин Дмитрий Александрович кандидат физико-математических наук, профессор С алий Вячеслав Николаевич

Ведущая организация: Уральский государственный университет

им. А.М.Горького

Защита состоится 2006 г. в Ж. час. ¿О мин.

на заседании диссертационного совета К 212.243.02 в Саратовском государственном университете им. Н.Г.Чернышевского по адресу: 410012, Саратов, ул. Астраханская, 83, Саратовский государственный университет им. Н.Г.Чернышевского.

С диссертацией можно ознакомиться в библиотеке Саратовского государственного университета им. Н.Г.Чернышевского.

Автореферат разослан »/Я " 2006 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент

Л/

В.В.Корнев

Общая характеристика работы.

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

X. Она называется функцией переходов автомата и показывает, как входной сигнал в преобразует состояние х в новое состояние х' = ¿'(г, я). Операция А - это функция от тех же переменных х е X, з 6 но со значениями А(х,«) в множестве выходных сигналов У. Она называется выходной функцией автомата А и указывает значение сигнала на выходе у = А(х, в) в зависимости от состояния автомата х и значения входного сигнала

и нечетких автоматов ¡11]. Исследованиям таких автоматов посвящены, например, работы Сперанского Д.В., Сытника A.A., Плоткина Б.И. и Филькенштейна М.Я., Гечега Ф., Каца М.М. и многих других. В общем случае автоматы, основные множества которых наделены дополнительной алгебраической структурой, называются структуризованнымн автоматами. Многочисленные исследования в этом направлении характеризуются широким использованием алгебраических средств, и, таким образом, автомат - один из основных объектов математической кибернетики - становится предметом научного интереса алгебраической теории автоматов, которая непосредственно связана с важными разделами универсальной алгебры [9] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, связанным с их поведением, анализом и синтезом, к теории языков и алгоритмов и ко многим другим разделам математической кибернетики.

В настоящей работе продолжается исследование этого направления: здесь изучаются алгебраические свойства так называемых упорядоченных автоматов, т.е. автоматов, у которых множество состояний и множество выходных сигналов наделены алгебраической структурой упорядоченного множества, которая сохраняется функциями переходов и выходными функциями этих автоматов.

изучению математических объектов путем исследования некоторых производных алгебр отображений, специальным образом связанных С исходными объектами. В нашем примере изучаемым математическим объектом является универсальный упорядоченный полуавтомат А1ш(Х) и производной алгеброй отображений - его полугруппа входных сигналов ЕпсЦГ. Следовательно, алгебраическая теория упорядоченных автоматов тесным образом связана с общеизвестной задачей определяемости математических объектов их эндоморфизмами и автоморфизмами, которая сформулирована в числе прочих актуальных математических проблем в известной книге С. Улама 113].

Проведенные в работе исследования универсальных упорядоченных автоматов следуют уже сложившемуся традиционному кругу вопросов обобщенной теории Галуа: принципиальное значение имеет задача о том, как производная алгебра отображений определяет исходный объект; затем исследуется, какими абстрактными свойствами характеризуется такая производная алгебра отображений; наконец, с помощью полученных результатов изучаются взаимосвязи свойств исходного объекта и его производной алгебры отображений. Такие вопросы для групп автоморфизмов алгебраических систем, полугрупп эндоморфизмов графов, колец линейных преобразований векторных пространств и других алгебр преобразований весьма успешно решались Б.И.Плоткиным [12], Л.М.Глускиным [5], Ю.М.Важениным [2] и другими авторами. Особое внимание в этом направлении уделялось изучению групп автоморфизмов и полугрупп эндоморфизмов графов: в работе [18] Р.Фрухт доказал, что для любой конечной абстрактной группы существует граф, труппа автоморфизмов которого 'изоморфна данной группе, и в работе [15] З.Хедрлин и А.Пультр доказали, что для любой конечной абстрактной полугруппы с единицей существует граф, полугруппа эндоморфизмов которого изоморфна данной полугруппе. Эти результаты дают абстрактную характеризацию групп автоморфизмов и полугрупп автоморфизмов графов и имеют непосредственное отношение к поставленному Д.Кен игом в [16] вопросу: каким условиям должна удовлетворять группа подстановок из п элементов, чтобы существовал п-вершинный граф, группа автоморфизмов которого совпадает с этой группой подстановок? В более общей форме эта задача формулируется В.Г.Визингом |3] следующим образом : дана группа подстановок; найти все графы, для которых данная группа является группой автоморфизмов. Эта известная и до сих

пор не решенная задача является частным случаем сложной проблемы конкретной характершации [14) производных алгебр отображений в обобщенной теории Галуа, т.е. проблемы описания таких условий, при которых алгебра отображений равна производной алгебре отображений изучаемого математического объекта. В этом направлении отдельные продвижения были сделаны М.Краснером [17], Е.С.Ляпиным [10], Б.Йонсоном [14], Д.Бредихиным [1] и другими авторами для полугрупп эндоморфизмов релятивов, групп автоморфизмов и инверсных полугрупп частичных автоморфизмов универсальных алгебр. К этому же направлению относится задача упорядочиваемостн полуавтоматов, исследованная М.М.Кацем [8].

при каких условиях полуавтомат А с множеством состояний X и полугруппой входных сигналов S, рассматриваемой как полугруппа преобразований множества Xt является универсально упорядочиваемым полуавтоматом, т.е. на множестве состояний автомата А можно так определить нетривиальное отношение порядка <, что полугруппа эндоморфизмов End X упорядоченного множества X — (X, <) совпадет с полугруппой входных сигналов автомата Л?

Главным инструментом решения сформулированной задачи является разработанная в диссертации техника канонических отношений полугрупп преобразований, которые определяются в исходных полугруппах формулами языка узкого исчисления предикатов (УИП). Такое решение поставленной задачи дает эффективный метод последовательного изучения взаимосвязи свойств универсальных упорядоченных полуавтоматов и их полугрупп входных сигналов.

В работе изучаются также универсальные упорядоченные автоматы, подавтоматы которых охватывают гомоморфные образы всех упорядоченных полу групповых автоматов с выходными сигналами. Такие универсальные упорядоченные автоматы являются структуризованными автоматами Atm(.X, У) = (X, S, Y, 6, А) с упорядоченным множеством состояний X — (X, <х), упорядоченным множеством выходных сигналов У = (Kir)» полугруппой входных сигналов S = EndX х Нош{ЛГ,У) (состоящей из nap s = (ip, -ф) эндоморфизмов <р упорядоченного множества X и гомоморфизмов if>

упорядоченного множествав упорядоченное множество У), функцией переходов 6(х, з) — <р(х) и выходной функцией А (ж, 5) = ф(х) (здесь х € X и з = (V?, - элемент полугруппы 5 = Еп<1Х х Нот(Х, У)).

Особое внимание в этом направлении уделяется исследованию вопроса о том, как универсальные упорядоченные автоматы определяются своими полугруппам« входных сигналов, и решению задачи конкретной характеризации таких автоматов, которая формулируется следующим образом:

при каких условиях автомат А — (X, У, 5, А) с множеством состояний X, множеством выходных сигналов У и полугруппой входных сигналов 3 является универсально упорядочиваемым автоматом?

Цель работы. Разработать алгебраические методы исследования универсальных упорядоченных автоматов. Решить задачу конкретной характеризации универсальных упорядоченных автоматов. Изучить взаимосвязь свойств универсальных упорядоченных автоматов со свойствами их полугрупп входных сигналов.

Методы исследования. В работе используются известные методы универсальной алгебры, алгебраической теории автоматов и алгебры отношений.

Научная новизна. Все результаты диссертации являются новыми. Основные результаты диссертации:

1) решена задача конкретной характеризации универсальных упорядоченных полуавтоматов;

2) доказана относительно элементарная определимость класса универсальных упорядоченных полуавтоматов в классе полугрупп;

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

4) исследован вопрос о том, как универсальные упорядоченные автоматы определяются своими полугруппами входных сигналов;

5) описано строение изоморфизмов универсальных упорядоченных автоматов;

6) решена задача конкретной характеризации универсальных упорядоченных автоматов.

Теоретическая и практическая ценность. Диссертация носит теоретический характер. Полученные результаты могут быть использованы в алгебраической теории автоматов и теории полугрупп.

Апробация работы. Результаты диссертации докладывались на секции "Алгебраические аспекты теории управляющих систем" научных конференций механико-математического факультета Саратовского государственного университета (2003, 2004, 2005, 2006), на секции "Проблемы теоретической кибернетики" научной конференции Саратовского государственного социально-экономического университета

(2005), на объединенном семинаре Саратовского государственного университета по дискретной математике и математической кибернетике

(2006).

Диссертация выполнена в рамках научно-исследовательской темы Федерального агентства по образованию "Нестандартная теория многосортных алгебраических систем и ее приложения к компьютерной науке" (№ госрегистрации 01.200.201962) и проекта ИНТАС "Комбинаторная и геометрическая теории групп и полугрупп и их приложения к компьютерной алгебре", грант 99-1224.

Публикации. Основные результаты диссертации опубликованы в работах [А1] - [А7].

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы из 29 наименований. Общий объем диссертации 99 страниц.

Основное содержание работы.

Во введении обосновывается актуальность темы и дается краткое содержание диссертации.

В первой главе излагаются основные алгебраические понятия, необходимые для последовательного развития алгебраической теории упорядоченных автоматов. Здесь уточняется общепринятая терминология и приводятся необходимые определения и обозначения из алгебры отношений, теории упорядоченных множеств, теории автоматов и теории мпогоосновных алгебр.

Под отношением порядка на множестве X в работе понимается рефлексивное, транзитивное и антисимметричное бинарное отношение рСХхХ, которое обозначается также символом < . Отношение порядка называется нетривиальным, если оно отлично от тождественного отношения Ах на множестве X.

Эндоморфизмом упорядоченного множества X = (А", <) называется преобразование / множества X, удовлетворяющее при любых значениях х,у 6 X условию: х < у => /(х) < /(у). Множество всех

таких эндоморфизмов с операцией композиции образует полугруппу, которая обозначается символом End X и называется полугруппой эндоморфизмов упорядоченного множества X.

Для упорядоченных множеств X,Y символом Нот(ЛГ, У) обозначается множество всех гомоморфизмов Л" в У, Известно [11], что множество S — End А" х Нош(АГ, У) является полугруппой с операцией умножения которая для элементов (v'bV'i)» (Уг^) € S определяется по формуле: • = (<PW2,<Piip2)-

Под упорядоченным автоматом будем понимать, следуя [11], упорядоченный полугрупповой автомат, т.е. алгебраическую систему вида А = (ЛТ, S, У, 6, А), где X — {Х,<х) ~ упорядоченное множество состояний автомата, S — (5, •) — полугруппа входных сигналов, У = (У, <у) - упорядоченное множество выходных сигналов, S : X х S —* X - функция переходов и А ; Jf х S -»У - выходная функция, удовлетворяющие при всех х, у 6 X, s, s' G S, условиям;

s ■ б') — 5(6(х, s), s'), \{х, s ■ s') = Л(£(лг, s),s')) и при фиксированном значении s отображение = ¿(х, $) (х 6 X) является эндоморфизмом упорядоченного множества X, отображение А,(х) = A(x,s) (х £ X) - гомоморфизмом X в У. Автоматы без выходных сигналов называются полуавтоматами.

Во второй главе диссертации рассматриваются упорядоченные полу групповые полуавтоматы.

Основное внимание здесь уделяется универсальным упорядоченным полуавтоматам, т.е. автоматам вида Atm (X) — (X, End Л', 5), где X — (X, <} - упорядоченное множество состояний, End X - полугруппа входных сигналов и функция переходов для элементов х 6 X, 6 End X определяется по формуле 6(х, <р) = <р(т).

Центральный результат этой главы дает решение задачи конкретной характеризации универсальных упорядоченных полуавтоматов.

Пусть S - некоторая полугруппа преобразований множества X. Символом Q обозначим бинарное отношение на множестве X, которое состоит из всех таких пар (х,у) 6 Xs, что для любых элементов u,v е X, и ф v найдется преобразование f € S, отображающее множество {u,v} на множество {х,у}. Полугруппа S называется Q-замкнутой, если для любого преобразования f множества X из условия, что для любых х, у £ X, удовлетворяющих (ж, у) € Q, существует преобразование <р в S такое, что ограничение <р | {х,у} совпадает с ограничением / | {х, у), следует / € S.

Теорема 2.6. Полуавтомат А = (X, S, <5) без равнодействующих

входных сигналов в том и только том случае будет универсально упорядочиваемым, если полугруппа входных сигналов S является Q-замкнутой полугруппой и ее каноническое отношение Q удовлетворяет следующим условиям:

(j4i) (я, л) € Q для любого

(Ла) если x,y,u,v - любые элементы из X, причем и ф v и существуют отображения /,д такие, что /(х) = и, f(y) = v, д{х) =t),g(y> = и, то (ж, у) £ Q\

(Лз) если x,y,u,v,w - любые элементы из А', для которых (х,у), (u, u), (v, w) 6 Q, и существуют отображения f,g такие, что f(x) = ы, J(y) ~ и, g(x) = v, g(y) = w, то существует отображение h такое, что h(x) = гц h(y) — го;

(Aj) существуют х, у 6 X, удовлетворяющие х ф у и € Q-

В разделе 2.2 получена абстрактная характеристика универсальных упорядоченных полуавтоматов. Рассмотрим формулы языка элементарной теории полугрупп:

М{х) = (V у) (ух = х),

П(х1,х2;хз,х4) = (М(х\) Л М(х%) Л Л/(хз) Л Л (3f)(xif = хз Л x2f = х4)), я(Х,у) = (М(х) Л ЛГ(у) A (Vu, v, и ф v)(M(it) Л M(v) (П(и, v; х, у) V П(и,«; х, у)))).

Теорема 2.9. Произвольный полуавтомат А = {X, S, S) в том и только том случае изоморфен универсальному нетривиально упорядоченному полуавтомату, если он удовлетворяет следующим аксиомам:

(л!) (Vx 6 A')(3!s е S)(Vy € X) ( s) = x)-,

M (x) A M{y) A M(u) A M(v) Л (и Ф v) A (3 f,g) (х/ = и A A yf = v A xg = v А уд = ti) g(x, ¡/);

(Л^) q(x,y) A q(u,v) A q(v,w) A (3 f,g) (if = и A yf = v A A xg = v A yg = tu) (3ft)(xA = иЛ yh = to);

(A^ {Bx,y) (z^yAfofoiO);

(j?s) для любого преобразования tp множества X выполняется условие

. (Vx, у .6 Х)(д(х,у) (3s S S)(5(a\ s) = ^(i) Л ¿(у, s) = у>(г/)) (3!Л € S)(Vz e ДГ)(г(г, h) « <р(я)).

С целью последовательного изучения взаимосвязи абстрактных и элементарных свойств универсальных упорядоченных полуавтоматов и их полугрупп входных сигналов в разделе 2.3 доказана относительно элементарная определимость [7] класса таких полуавтоматов в классе всех полугрупп.

Теорема 2.17. Существуют такие формулы

M(x)t D(x, у, г), Р(и, v; х, у)

сигнатуры языка элементарной теории полугрупп что для

любого универсального упорядоченного полуавтомата А = Atm(Jf) с нетривиально упорядоченным множеством состояний X — (X, <х) и полугруппой входных сигналов S — End А* выполняются следующие условия:

1) множество X = {х 6 S : Л/(я-)} не пусто;

2) формула D(x, yyz) задает тернарное отношение 6 с ~Х х S X X, удовлетворяющее условию

(я.ьг,*!),(l,!f,z2)ei => zl - z2;

3) в полугруппе 5 входных сигналов полуавтомата А найдутся такие элементы Хо, ifoi что формула Р(хо, х, у) задает отношение порядка < на множестве X, для которого упорядоченный полуавтомат А = (X, S, 5) изоморфен универсальному упорядоченному полуавтомату А = Atm(A');

5) для любой формулы Ф языка элементарной теории упорядоченных полуавтоматов эффективно строится такая формула языка элементарной теории полугрупп, что если Ф истинна на универсальном упорядоченном полуавтомате А, то формула Ф истинна на его полугруппе входных сигналов 1пр(Д) н, с другой стороны, если ф истинна на полугруппе Inp(A), то на универсальном упорядоченном полуавтомате А истинна формула Ф или двойственная ей формула Ф (которая получается из формулы Ф заменой атомарных подформул х < у формулами у < ¡с).

С помощью этого результата в разделе 2.4 исследованы задачи об определяемое™ универсальных упорядоченных полуавтоматов своими полугруппами входных сигналов, которые непосредственно связаны с известными результатами Л.М.Глускина [4] и Ю.М.Важенина [2j.

Теорема 2.19. Пусть Xi, — упорядоченные множества, причем порядок на одном из множеств Xi,X% отличен от тождественного. Тогда для универсальных упорядоченных полуавтоматов Ai — Atm(Xi), Лг = Atm(Xa) следующие условия эквивалентны;

1) полугруппы Inp(j4i), Inp(j4a) входных сигналов полуавтоматов Ах, Аг элементарно эквивалентны,

2) полуавтомат Ai элементарно эквивалентен полуавтомату А% или двойственному для него полуавтомату Л^.

В третьей главе диссертации приводятся результаты последовательного изучения универсальных упорядоченных полугрупповых автоматов, т.е. автоматов вида Atm(X) = (X, S,Y,5, А), где X ~ (X, <х) - упорядоченное множество состояний, У = (У, <у) -упорядоченное множество выходных сигналов, полугруппа входных сигналов S - есть полугруппа End X к Нот(Х, У) и функция переходов $ и выходная функция Л для элементов х 6 X, (<р, ф) б S определяются по формулам: б(х, ip)) = <р(х), Л(х, (¡р,-ф)) = -ф{х).

В разделе 3.1 исследован вопрос о том, как универсальные упорядоченные автоматы определяются своими полугруппами входных сигналов. Полученный результат обобщает известный результат Глускина J1.M. [4] об универсальных упорядоченных полуавтоматах на универсальные упорядоченные автоматы.

Теорема 3.2. Пусть Xi,Yi,Xi, Уг - универсальные упорядоченные множества, причем порядок на одном из множеств Х\,Хъ отличен от тождественного. Тогда для универсальных упорядоченных автоматов

= Atm(JVi,yi)t = Atm(Xi,>2) следующие условия эквивалентны:

1) полугруппы входных сигналов автоматов AitA2 изоморфны;

2) упорядоченные множества X\tY\ соответственно изоморфны упорядоченным множествам Хг, >2 или упорядоченным множествам

3) автомат Ai изоморфен автомату Аз или автомату

Аг = Atm(^s. Уз)-

В разделах 3.2 и 3.3 изучаются изоморфизмы и группы автоморфизмов универсальных упорядоченных автоматов.

Исчерпывающее описание строения изоморфизмов полугрупп входных сигналов универсальных упорядоченных автоматов дает следу ющий результат.

Теорема 3.7. Пусть Х\,Х2,У\,Уа ~ произвольные упорядоченные множества, причем множество Х\ нетривиально упорядочено и имеет компоненты связности {-Хц}|е|, и пусть А1т(Л"1, У1), А'Ьт^Л'г, Уз) ~~ универсальные упорядоченные автоматы с полугруппами входных сигналов= ЕпаА"! х Нош(А'1, Уг), = Ен^Ха * Нот(АГг, У2). ТЬгда отображение тг : —► в том и только том случае является изоморфизмом полугруппы 3\ на полугруппу если для некоторого изоморфизма (или антиизоморфизма) / упорядоченного множества Х\ на упорядоченное множество Л'а и некоторого семейства изоморфизмов (соответственно, антиизоморфизмов) & (( 6 /) упорядоченного множества У! на упорядоченное множество значение 7г(</?, ■ф) для элементов {у}, ф) е 5] определяется по формуле:

где ^(/(а)) = д(^(о)) для любого а € Х\ и значения г € удовлетворяющего условию <р(а) е Хи .

В разделе 3.4 приводится центральный результат третьей главы, который дает решение задачи конкретной характеризации универсальных упорядоченных автоматов.

Определим для автомата А = (Х,3, У,<£, А) два канонических бинарных отношения но формуле: пара элементов (х,у) из

множества X2 (соответственно, из Уг) принадлежит отношению С^х (соответственно, <5у), если для любых элементов е X, и / V найдется такой входной сигнал 8 е что отображение 6г

(соответственно, А,) отображает множество {«,«} на множество {ж,у!).

Теорема 3.17. Автомат А = (X, 5, У, А) без равнодействующих входных сигналов в том и только том случае будет универсально упорядочиваемым автоматом АЬт(Х, У), если канонические отношения автомата А удовлетворяют следующим схемам условий:

(Е1) для любого х<=2 выполняется (х, х) б Яг (здесь 2 е {X, У});

(Е3) если х,у - любые элементы из X, - любые элементы из ¿Г, причем и/ои существуют пары отображений /,д 6 3 такие, что

/{х) = и,/(у) = ь,д(х) = ь,д(у) = и, то выполняется условие (здесь 2 € {Х,У});

(Ез) если (х, у) е (¿х, и, V, ш - произвольные элементы 2, причем (и,«), (и,т) е <Эг и существуют пары отображений /, <7 € ¿¡* такие, что /(х) — «, /(у) = у, д(х) = V, д(у) = то существует пара отображений Л е 5 такая, что Л(х) = и, к(у) = ь> (здесь

(И|) существуют такие элементы х,у Е. X, что х фу, (х,у) € <5х;

(£5) для любой пары / = (/1, /а) отображений /1 : X —* X, /2 : X —* У из условия, что для любых х, у 6 X, удовлетворяющих (х,у) € , в полугруппе существует пара отображений <р = (^ь^г) такая, что ограничения ^ | {х,у} совпадают с ограничениями [ {х, у} (» = 1,2), следует /е5,

Автор выражает глубокую благодарность научному руководителю профессору Молчанову Владимиру Александровичу за постановку задач и поддержку в исследованиях.

Список литературы

[1] Бредихин Д А. Инверсные полугруппы локальных автоморфизмов универсальных алгебр. - Сибирск. матем. журнал, 1975, т.17, №3, с.490-507.

[2] Важенин Ю.М., Элементарные свойства полугрупп преобразований упорядоченных множеств // Алгебра и логика. 1970. Вып. 9, №3. С. 281-301.

[3] ВизингВ.Г. Некоторые нерешенные задачи в теории графов.-УМН, 1968, т. 23, №6, с. 117-134.

[4] Глускин Л.М. Полугруппы изотонных преобразований // УМН. 1961. Т.16, №5. С.157-162.

[5] Глускин Л.М., Полугруппы и кольца эндоморфизмов линейных пространств, Изв. АН СССР. Сер. мат. 1959. Т. 23. С. 841-870.

[6] Глушков В.М., Абстрактная теория автоматов // УМН. 1961. Т.16, №5. С. 3-62.

[7] Ершов Ю.Л.. Проблемы разрешимости и конструктивные модели. М.: Наука, 1980. - 320 с.

[8] Кац М.М., Критерий линейной упорядочиваемости частичного автомата, Изв.вузов. Математика. 1997. № 10. С. 37-43.

[9] Кон П., Универсальная алгебра. М.: Мир, 1968.

[10] Ляпин Е.С. В кн.: Резюме сообщений и докл. межвуз. научного симпозиума по общей алгебре, Тарту, 1966, с. 75-89.

[И] Плоткин Б.И., Грин глаз Л.Я., Гварамия A.A. Элементы алгебраической теории автоматов. М.:Высш. шк., 1994.

[12] Плоткин Б.И., Группы автоморфизмов алгебраических систем. М.: Наука, 1966.

[13] Улам С. Нерешенные математические задачи. М.: Наука, 1964.

[14] Jonson В., Topics in Univeraal Algebras. Lecture Notes, Vanderbilt University, 1969-1970.

[15] Hedrlin Z., Pultr A. Symmetrie reiations (undirected grapha) with given semigronp, Monatsh.Math., 69 (1965), 318-322.

[16] D.Konig, Theorie der endlichen und unendlichen Graphen, Leipzig, 1936.

[17] Krasner M., Endotheorie de GaJois abstraita. Semin. Dubriel, Dubriel-Jacotin, Lesieur et Pisot. Fac. sei. Paris. 1968-1969(1970). V. 22, N 1. S. 6/01-6/19.

[18] R.Frucht, Herstellung von Graphen mit vorgegebener abstrakten Gruppe, Comp. Math. 6 (1938), 239-250.

Публикации автора по теме диссертации.

[AI] Акимова С. А., Конкретная характеристика полугрупп эндоморфизмов упорядоченных множеств // Математика, механика: Сб. науч. тр. - Саратов: Изд-во Сарат. ун-та, 2003. Вып. 5. С. 3-5.

[А2] Акимова С. А., Абстрактная характеристика полугруппы эндоморфизмов упорядоченного множества // Математика, механика: Сб. науч. тр. - Саратов: Изд-во Сарат. ун-та, 2004. Вып. 6. С. 3-5.

[A3] Акимова С.А., Об определяемости универсальных упорядоченных автоматов полугруппами их входных сигналов // Международная алгебраическая конференция, посвященная 100-летию

со дня рождения П.Г.Конторовича и 70-летию Л.Н.Шеврина. Тезисы докладов. - Екатеринбург: Изд-во УрГУ, 2005. - С. 167-168.

[А4] Акимова С-А., Характеризация полугрупп эндоморфизмов упорядоченных множеств // СГУ. Саратов, 2005. Деп, в ВИНИТИ 26.09.2005, № 1252-В2005. 17 с.

[А5] Акимова С. А., Об определяемое™ универсальных упорядоченных автоматов полугруппами их входных сигналов // Изв. Волгоградского гос. пед. ун-та, №4 (13). 2005. Серия естественных и физико-математических наук. Стр. 24-27.

[А6] Акимова С.А., О характеризации упорядоченных автоматов // Социально-экономическое развитие России: Проблемы, поиски, решения: Об. науч. тр. - Саратов: Изд. центр Сарат. госуд. соц.-эконом. ун-та, 2005. Ч. 2. С. 105-106.

[А7] Акимова С. А., Группа автоморфизмов универсальных упорядоченных автоматов // Математическое и информационное обеспечение экономической деятельности: Альманах. Саратов: Саратовский государственный социально-экономический университет, 2006. С. 66-69.

Подписано в печать 14,10.2006 Формат 60x84 1/16. Бумага офсетная. Гарнитура Times. Печать RISO. Объем ) ,0 печ. л. Тираж 100 экз. Заказ № 072.

Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Сермаи Ю.Б. Свидетельство № 3117 410600, Сзрэтов, ул. Московская, д.152, офис 19, тел. 26-] 8-19,51-16-28

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Акимова, Светлана Александровна

Введение

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, S, Y, 5, Л) с тремя основными множествами X, S, Y и двумя бинарными операциями 5 : X х S —> X, X : X х S —> Y. При этом X называется множеством состояний автомата, S - множеством входных сигналов, Y - множеством выходных сигналов. Операция 6 - это функция от двух переменных х G X, s £ S со значениями д(х, s) в множестве состояний X. Она называется функцией переходов автомата и показывает, как входной сигнал s преобразует состояние х в новое состояние х' = 6(х, s). Операция Л - это функция от тех же переменных х £ X, s £ S, но со значениями Х(х, s) в множестве выходных сигналов У. Она называется выходной функцией автомата А и указывает значение сигнала на выходе у = \(х, s) в зависимости от состояния автомата х и значения входного сигнала s.

В зависимости от специфики рассматриваемых задач математической кибернетики, устройство преобразования информации может моделироваться автоматом, у которого множество состояний и множество выходных сигналов наделены дополнительной математической структурой (например, структурой линейного пространства, упорядоченного множества, топологического пространства и другими), которая сохраняется функциями переходов и выходными функциями этого автомата (см., например, известные работы В.М.Глушкова [9] и Б.И.Плоткина [20]). Так, известные конкретные задачи математической кибернетики приводят к понятиям линейных, упорядоченных, топологических, вероятностных и нечетких автоматов. Исследованиям таких автоматов посвящены, например, работы Скорнякова J1.A., Сперанского Д.В., Сытника А.А., Плоткина Б.И. и Филькенштейна М.Я., Гечега Ф., Каца М.М. и многих других. В общем случае автоматы, основные множества которых наделены дополнительной алгебраической структурой, называются структуризованными автоматами. Многочисленные исследования в этом направлении характеризуются широким использованием алгебраических средств, и, таким образом, автомат - один из основных объектов математической кибернетики - становится предметом научного интереса алгебраической теории автоматов, которая непосредственно связана с важными разделами универсальной алгебры [13] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, связанным с их поведением, анализом и синтезом, к теории языков и алгоритмов и ко многим другим разделам математической кибернетики.

В настоящей работе продолжается исследование этого направления: здесь изучаются алгебраические свойства упорядоченных автоматов, т.е. автоматов, у которых множество состояний и множество выходных сигналов наделены алгебраической структурой упорядоченного множества, которая сохраняется функциями переходов и выходными функциями этого автомата.

Основное внимание в настоящей работе уделяется так называемым универсальным упорядоченным автоматам, подавтоматы которых охватывают гомоморфные образы всех рассматриваемых упорядоченных автоматов. Например, при изучении упорядоченных полугрупповых автоматов без выходных сигналов (называемых также полуавтоматами [1]) таким универсальным упорядоченным автоматом является полуавтомат Atm(X) = {X, EndX, 5) с упорядоченным множеством состояний X = (X, <), полугруппой входных сигналов End X (состоящей из эндоморфизмов упорядоченного множества X) и функцией переходов 5(х,<р) = ip(x) (здесь х £ X, ip € End X), поскольку для любого упорядоченного полугруппового полуавтомата А = (X, S, 6) с упорядоченным множеством состояний X существует единственный гомоморфизм А в Atm(X). В таком контексте полугруппа EndX эндоморфизмов упорядоченного множества X играет определяющую роль для автоматов А с упорядоченным множеством состояний X. Поэтому алгебраическая теория универсальных упорядоченных автоматов имеет непосредственное отношение к одному из основных разделов современной алгебры - обобщенной теории Галуа, начало которой было положено в исследованиях Э.Галуа и которая посвящается изучению математических объектов путем исследования некоторых производных алгебр отображений, специальным образом связанных с исходными объектами. В нашем примере изучаемым математическим объектом является универсальный упорядоченный полуавтомат Atm(X) и производной алгеброй отображений - его полугруппа входных сигналов EndX. Следовательно, алгебраическая теория упорядоченных автоматов тесным образом связана с общеизвестной задачей определяемости математических объектов их эндоморфизмами и автоморфизмами, которая сформулирована в числе прочих актуальных математических проблем в известной книге С. Улама [23].

Проведенные в работе исследования универсальных упорядоченных автоматов следуют уже сложившемуся традиционному кругу вопросов обобщенной теории Галуа: принципиальное значение имеет задача о том, как производная алгебра отображений определяет исходный объект; затем исследуется, какими абстрактными свойствами характеризуется такая производная алгебра отображений; наконец, с помощью полученных результатов изучаются взаимосвязи свойств исходного объекта и его производной алгебры отображений. Такие вопросы для групп автоморфизмов алгебраических систем, полугрупп эндоморфизмов графов, колец линейных преобразований векторных пространств и других алгебр преобразований весьма успешно решались Б.И.Плоткиным [21], Л.М.Глускиным [7], Ю.М.Важениным [3] и другими авторами. Особое внимание в этом направлении уделялось изучению групп автоморфизмов и полугрупп эндоморфизмов графов: в работе [25] Р.Фрухт доказал, что для любой конечной абстрактной группы существует граф, группа автоморфизмов которого изоморфна данной группе, и в работе [26] З.Хедрлин и А.Пультр доказали, что для любой конечной абстрактной полугруппы с единицей существует граф, полугруппа эндоморфизмов которого изоморфна данной полугруппе. Эти результаты дают абстрактную характеризацию групп автоморфизмов и полугрупп автоморфизмов графов и имеют непосредственное отношение к поставленному Д.Кенигом в [28] вопросу: каким условиям должна удовлетворять группа подстановок из п элементов, чтобы существовал n-вершинный граф, группа автоморфизмов которого совпадает с этой группой подстановок? В более общей форме эта задача формулируется В.Г.Визингом [5] следующим образом: дана группа подстановок; найти все графы, для которых данная группа является группой автоморфизмов. Эта известная и до сих пор не решенная задача является частным случаем сложной проблемы конкретной характеризации [27] производных алгебр отображений в обобщенной теории Галуа, т.е. проблемы описания таких условий, при которых алгебра отображений равна производной алгебре отображений изучаемого математического объекта. В этом направлении отдельные продвижения были сделаны М.Краснером [29], Е.С.Ляпиным [16], Б.Йонсоном [27], Д.Бредихиным [2] и другими авторами для полугрупп эндоморфизмов релятивов, групп автоморфизмов и инверсных полугрупп частичных автоморфизмов универсальных алгебр. К этому же направлению относится задача упорядочиваемости полуавтоматов, исследованная М.М.Кацем [12].

Принципиальным отличием проведенных в диссертации исследований является положенное в их основу решение задачи конкретной характеризации универсальных упорядоченных автоматов. Для изучаемых в начале работы универсальных упорядоченных полуавтоматов такая задача формулируется следующим образом: при каких условиях полуавтомат А с множеством состояний X и полугруппой входных сигналов S, рассматриваемой как полугруппа преобразований множества X, является универсально упорядочиваемым полуавтоматом, т.е. на множестве состояний автомата А можно так определить нетривиальное отношение порядка <, что полугруппа эндоморфизмов EndX упорядоченного множества X = (X, <) совпадет с полугруппой входных сигналов автомата А?

В работе изучаются также универсальные упорядоченные автоматы, подавтоматы которых охватывают гомоморфные образы всех упорядоченных полугрупповых автоматов с выходными сигналами. Такие универсальные упорядоченные автоматы являются структуризованными автоматами Atm(X, У) = (X, S, У, д, Л) с упорядоченным множеством состояний X — (X, <х), упорядоченным множеством выходных сигналов У = (У, <у), полугруппой входных сигналов S = EndX х Hompsf,У) (состоящей из пар s = {(р^ф) эндоморфизмов ip упорядоченного множества X и гомоморфизмов ф упорядоченного множества X в упорядоченное множество У), функцией переходов 6(x,s) = tp(x) и выходной функцией X(x,s) = ф(х) (здесь х е X и s = (ip, ф) - элемент полугруппы S = EndX х Нот(Х, У)).

Для таких универсальных упорядоченных автоматов в первую очередь исследован вопрос о том, как универсальные упорядоченные автоматы определяются своими полугруппами входных сигналов?

В результате решения этой задачи в работе также описаны строения изоморфизмов универсальных упорядоченных автоматов и групп их автоморфизмов.

Особое внимание в работе уделено исследованию проблемы конкретной характеризации универсальных упорядоченных автоматов, которая формулируется следующим образом: при каких условиях автомат А = (X, S, У, S, Л) с множеством состояний X, множеством выходных сигналов У и полугруппой входных сигналов S является универсально упорядочиваемым автоматом?

Идея решения задачи заключается в том, что по полугруппе входных сигналов автомата А на его множествах X, У строятся канонические отношения и с их помощью формулируются необходимые и достаточные условия, при которых на этих множествах X,Y существуют такие отношения порядков, что полугруппа S совпадает с полугруппой EndX х Hom(X, Y).

В первой главе работы излагаются основные алгебраические понятия, необходимые для последовательного развития алгебраической теории упорядоченных автоматов. Здесь уточняется общепринятая терминология и приводятся необходимые определения и обозначения из алгебры отношений, теории упорядоченных множеств, теории автоматов и теории многоосновных алгебр.

Во второй главе диссертации рассматриваются универсальные упорядоченные полуавтоматы. Центральный результат этой главы дает решение задачи конкретной характеризации таких автоматов. Главным инструментом решения сформулированной задачи является разработанная в диссертации техника канонических отношений полугрупп преобразований.

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

В разделе 2.3 с помощью полученной в теореме 2.6 конкретной характеристики универсальных упорядоченных полуавтоматов доказана относительно элементарная определимость [10] класса таких полуавтоматов в классе всех полугрупп с целью дальнейшего изучения взаимосвязи абстрактных и элементарных свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов.

В разделе 2.4 с помощью относительно элементарной определимости класса универсальных упорядоченных полуавтоматов в классе полугрупп исследованы задачи о взаимосвязи свойств универсальных упорядоченных полуавтоматов и полугрупп их входных сигналов, которые непосредственно связаны с известными результатами Л.М.Глускина [6] и Ю.М.Важенина [3].

В третьей главе диссертации приводятся результаты последовательного изучения универсальных упорядоченных автоматов. В разделе 3.1 исследован вопрос о том, как универсальный упорядоченный автомат определяется своей полугруппой входных сигналов. Полученный результат обобщает известный результат Глускина J1.M. [6] об определяемости упорядоченных множеств полугруппами их эндоморфизмов.

В разделе 3.2 изучается взаимосвязь изоморфизмов универсальных упорядоченных автоматов с изоморфизмами их полугрупп входных сигналов и изоморфизмами их упорядоченных множеств состояний и упорядоченных множеств выходных сигналов.

В разделе 3.3 описывается строение групп автоморфизмов универсальных упорядоченных автоматов.

Полученные результаты решают ряд принципиальных вопросов о взаимосвязи упорядоченных автоматов с их полугруппами входных сигналов, а также дают весьма эффективный инструмент для дальнейшего разностороннего исследования этой проблематики в алгебраической теории автоматов и для разнообразных приложений к комбинаторному исследованию автоматов, к изучению вопросов классификации автоматов средствами языка УИП и к анализу проблем разрешимости элементарных теорий классов автоматов.

Сделаем несколько замечаний технического характера. Справка об основных понятиях и обозначениях, систематически используемых в диссертации, дается в разделе "Основные понятия". Более специальные определения приводятся в начале каждой главы. Нумерация теорем, лемм и следствий в диссертации сквозная с учетом номера главы, нумерация формул своя в каждой главе. Например, ссылка "теорема 2.6"означает теорему 2.6 из главы 2. Окончание доказательства обозначается символом □.

Результаты диссертации докладывались на секции "Алгебраические аспекты теории управляющих систем" научных конференций механико-математического факультета Саратовского государственного университета (2003, 2004, 2005, 2006), на секции "Проблемы теоретической кибернетики" научной конференции Саратовского государственного социально-экономического университета (2005), на объединенном семинаре Саратовского государственного университета по дискретной математике и математической кибернетике (2006).

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

В этой главе излагаются основные понятия, необходимые для последовательного развития алгебраической теории упорядоченных автоматов. Здесь уточняется общепринятая терминология и приводятся необходимые определения и обозначения из алгебры отношений, теории упорядоченных множеств и теории автоматов.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Акимова, Светлана Александровна, Саратов

1. Богомолов А.Н., Салий В.Н. Алгебраические основы теории дискретных систем. - М.:Наука. Физматлит, 1997.

2. Бредихин Д.А. Инверсные нолугрунпы локальных автоморфизмов универсальных алгебр. - Сибирск. матем. журнал, 1975, т.17, JY^ З,с.490-507.

3. Важенин Ю.М. Элементарные свойства нолугрунн нреобразований унорядоченных множеств. - Алгебра и логика, Новосибирск, 1970,Т.9, №3, с. 281-301.

4. Важенин Ю.М. Об элементарной онределяемости и элементарной характеризуемости классов рефлексивных графов. - Изв. высшихучебных заведений, Матем., 1972, № 7, с. 3-11.

5. Визинг В.Г. Некоторые нерешенные задачи в теории графов. - УМН, 1968, Т.23, X 6^, с. 117-134.

6. Глускин Л.М. Нолугрунны изотонных преобразований. -УМН, 1961, Т.16, № 5, с. 157-162.

7. Глускин Л.М. Полугруппы и кольца эндоморфизмов линейных пространств. Изв. АН СССР. Сер. мат. 1959. Т.23. 841-870.

8. Глускин Л.М. Идеалы полугрупп. - Матем.сб., 1961, т. 55, № 4, с. 421- 448.

9. Глушков В.М., Абстрактная теория автоматов // УМН. 1961. Т.16, №5. 3-62.

10. Ершов Ю.Л., Проблемы разрешимости и конструктивные модели. - М., Наука, 1980. - 320 с.И. Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.АЭлементарные теории // Успехи мат. наук. - 1965. - Т. 20. - № 4.- 37-108.

11. Кац М.М., Критерий линейной упорядочиваемости частичного автомата. Изв.вузов. Математика. 1997. № 10. 37-43.95

12. Кон П., Универсальная алгебра. - М., Мир, 1968.

13. Лидл Р., Пильц Г. Прикладная абстрактная алгебра: Учеб. нособие / Пер. с англ. - Екатеринбург: Изд-во Урал, ун-та, 1996.

14. Лянин Е.С. Абстрактная характеристика некоторых полугрунн преобразований. - Ученые заниски ЛГПИ, 1955, т.ЮЗ, с.5-29.

15. Лянин Е.С. В кн.: Резюме сообщений и докл. межвуз. научного симпозиума но общей алгебре. Тарту, 1966, с. 75-89.

16. Мальцев А.И. Алгебраические системы. - М.: Наука, 1970. - 392 с.

17. Мальцев А.И. Симметрические группоиды. - Матем. сб., 1952, т.31, с.136-151.

18. Молчанов В.А. Нестандартные многообразия тонологических алгебраических систем // Изв. РАЕП. Серия МММИУ. Т.З. 1999.т. 14-45.

19. Плоткин В.И., Гринглаз Л.Я., Гварамия А.А. Элементы алгебраической теории автоматов.-М.:Высш. шк., 1994.

20. Плоткин Б.И., Группы автоморфизмов алгебраических систем. М.: Паука, 1966.

21. Робинсон А., Введение в теорию моделей и метаматематику алгебры. - М., Паука, 1967. - 376 с.

22. Улам Нерешенные математические задачи. М.: Наука, 1964.

23. Харари Ф. Теория графов.-М.:Мир, 1973.

24. Frucht R. Herstellung von Graphen mit vorgegebener abstrakten Gruppe, Сотр. Math. 6 (1938), 239-250.

25. Hedrlin Z., Pultr A. Symmetric relations (undirected graphs) with given semigroup, Monatsh.Math., 69 (1965), 318-322.

26. Jonsson В., Topics in universal algebra. Lecture Notes in Math.250, Springer - Verlag (Berhn - Heidelberg - New York, 1972).96

27. Konig D., Theorie der endlichen und unendlichen Graphen, Leipzig, 1936.