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

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

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

Введение

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 описывается строение групп автоморфизмов универсальных упорядоченных автоматов.

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

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

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

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

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

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

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

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.