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

• Отрыванкина, Татьяна Михайловна
• кандидат физико-математических наук
• 2000

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

Введение.

Глава 1. Основные понятия

1.1 Категории структуризованных автоматов.

1.2 Принципы нестандартного анализа.

1.3 Топологические алгебраические автоматы

Глава 2. Минимизация топологических алгебраических автоматов 2.1 Эквивалентные автоматы

2.2 Конструкция минимального автомата.

2.3 Основная теорема.

Глава 3. Универсальные объекты в категориях топологических алгебраических автоматов

3.1 Универсальный функтор. Теорема существования

3.2 Неетандартные многообразия топологических алгебраических автоматов

Глава 4. Классы конечных алгебраических автоматов

4.1 Псевдомногообразия конечных алгебраических автоматов

4.2 Решетки псевдомногообразий конечных алгебраических автоматов

Введение диссертации (часть автореферата) на тему «Универсальные объекты в категориях структуризованных автоматов»

Диссертация посвящена приложениям методов универсальной алгебры к теории автоматов.

Теория автоматов представляет собой один из основных разделов математической кибернетики. Главным объектом изучения этой теории является устройство, предназначенное для преобразования информации. Такие устройства, естественным образом возникают в многочисленных задачах, связанных с вычислительной техникой и управлением, в задачах теории связи и многих других [14]. В общем случае устройство преобразования информации может находится в различных состояниях, которые изменяются под влиянием определенных внешних воздействий (входных сигналов) и, в свою очередь, сами воздействуют на внешнюю среду (с помощью выходных сигналов). Математической моделью такого устройства является особая многоосновная система Л = (S, X. Y.S. Л), называемая автоматом. Три основных множества 5, X, У называются, соответственно, множеством состояний, множеством входных сигналов и множеством выходных сигналов автомата. Бинарные операции ö : S х X —У 5, А : S х X —> У называются функцией переходов и выходной функцией.

В теории автоматов и ее приложениях, наряду с классическим понятием автомата, у которого основные множества S, X, У являются аморфными конечными множествами, рассматриваются также автоматы, у которых множества состояний, входных и выходных сигналов наделены дополнительной математической структурой, сохраняющейся функциями 8 и Л. В качестве таких дополнительных структур могут выступать, например, алгебраические структуры конечного поля или линейного пространства, реляционные структуры упорядоченного множества или толерантного пространства, топологические структуры топологических групп или топологических векторных пространств и т.д. Автоматы, наделенные такими дополнительными структурами, называются, соответственно, автоматами над конечными полями, линейными автоматами, упорядоченными автоматами, толерантными автоматами, топологическими автоматами и топологическими линейными автоматами. Исследованиям таких автоматов посвящены, например, работы Плоткина Б.И. [24], Сперанского Д.В. [27], Гечега Ф. [6, 7], Каца М.М. [10], Арбиба М. [31], Сытника A.A.

Г991 Т/Т АДТТПГТДУ 7ТГГМЧ"*Т,ГУ Н П?ТГТТР>Л,Т п Г!"ЦЯР ЯПТЛИЯТИ ПСИППИИР Л/ГНТГЖ'^Г"

V J XX 1У1 X ХУУ X ^ X V • ЛГ ЧУ V/ I | X ^ЧЧУ и^и X V-» ¿«X X Х^Х ^ V V XX Х-/X X I А*Х XX тва которых наделены дополнительной математической структурой, называются структурированными автоматами. Многочисленные исследования в этом направлении характеризуются широким использованием алгебраических средств, и, таким образом, автомат - один из основных объектов математической кибернетики — становится предметом научного интереса алгебраической теории автоматов, которая непосредственно связана с важными разделами универсальной алгебры [13] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, к вопросам их декомпозиции и классификации, к теории языков и алгоритмов.

В настоящей работе продолжается изучение структуризованных автоматов, основные множества которых наделены как алгебраической, так и топологической структурами. Целью диссертационной работы является исследование категорий топологических алгебраических автоматов с целью разработки техники построения универсальных объектов таких категорий. Особый интерес к этой тематике объясняется тем, что понятие универсального объекта играет центральную роль в многочисленных приложениях теории категорий к теории автоматов, поскольку оно отражает наиболее важные свойства изучаемых автоматов. Например, минимальные автоматы являются универсальными притягивающими объектами в категориях эквивалентных автоматов, которые полностью определяют функции экспериментов таких автоматов. С другой стороны, свободные автоматы являются универсальными отталкивающими объектами в категориях автоматов, замкнутых относительно формирования гомоморфных образов, подсистем и прямых произведений (называемых кратко Н8Р-замкнутыми категориями или многообразиями), которые характеризуют элементарные свойства таких автоматов, выражающиеся тождествами языка логики узкого исчисления предикатов (УМП). В результате построение таких свободных автоматов является основой реализации важнейшей концепции в изучении категорий автоматов, которая (в форме известной теоремы Биркгофа [33]) отражает тесную взаимосвязь семантического подхода к изучению НБР-замкнутых классов автоматов и синтаксического подхода к изучению классов автоматов, определяемых множествами тождеств. Показательно, что перенос такого двойственного подхода к изучению автоматов на случай категорий конечных автоматов, замкнутых относительно формирования подсистем, гомоморфных образов и конечных прямых произведений (называемых кратко НЗРяп-замкнутыми категориями или псевдомногообразиями), представляет особый интерес не только для теории автоматов, но и для такого важнейшего направления теоретической компьютерной науки, как теория распознаваемых языков, поскольку известное соответствие Эйленберга [35] устанавливает тесную взаимосвязь между многообразиями распознаваемых языков и псевдомногообразиями соответствующих алгебр. Хорошо известно, что такие категории в общем случае не имеют универсальна/отталкивающих объектов и поэтому в теории псевдомногообразий возникает важнейшая задача построения аналогов таких универсальных

V» ТЧ объектов вне рассматриваемых категории. ГазнооОразные подходы к решению этой актуальной проблемы были разработаны Эйлеибергом С. и Шютценберже М.П. [36], Ашем К.Дж. [32], Рейтерманом Дж. [41]. Алмейдой Дж. [30] и другими. Унифицированный подход к теории топологических алгебраических систем и к теории псевдомногообразий разработал Молчанов В. А. на основе методов нестандартного анализа [2]. Распространение в настоящей работе этого нестандартного подхода на топологические алгебраические автоматы позволяет сводить упомянутую выше проблематику теории таких автоматов к вопросам теории нестандартных многообразий топологических алгебраических автоматов и эффективно проводить исследования в этом направлении логико-алгебраическими методами нестандартного анализа.

Целью работы является разработка нестандартных методов построения универсальных объектов в категориях структуризованных автоматов и решение с их помощью следующих задач:

- найти условие существования минимального автомата в классе эквивалентных топологических алгебраических автоматов и описать его строение;

- доказать существование универсального функтора представления категорий в категориях топологических алгебраических автоматов;

- доказать существование автомата, порожденного топологическими пространствами и определяющими (алгебраическими и топологическими) соотношениями;

- обобщить известную теорему Биркгофа о структурной характе-ризации многообразий алгебраических автоматов на случай нестандартных многообразий топологических алгебраических автоматов;

- обобщить разработанный Молчановым В.А. нестандартный под

Л'ПГТ V ТРППИИ Г\п и ГТПЛ Л ИП ГГ) ПЯТ Ы ТД ЬТ|ЦРШП,ТУ я ттт^Гт хтя г-ттл.гттяхт ттгч=>тг

IV Д. ^ и ,1, V? IIV/1 ИЧ^АХЧ/ XII ^ к- V» X Л Ч^У -3- ^ Л^иЛи/ домногообразий конечных алгебраических автоматов;

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Отрыванкина, Татьяна Михайловна, 2000 год

1. Алгебраическая теория автоматов! языков и полугрупп / под ред. М.А, Арбиба: Пер. с англ. М., Статистика, 1975.

2. Альбеверио С., Фенстад И., Хеэг-Крон Р., Линдстрем Т. Нестандартные методы в стохастическом анализе и математической физике. М.: Мир, 1990.

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

4. Бухараев Р.Г., Основы теории вероятностных автоматов. М., Наука, 1985.

5. Вагнер В.В., Теория отношений и алгебра частичных отображений // Теория полугрупп и ее приложения. Вып. 1. Саратов: Изд-во Сарат. гос. ун-та, 1965. С. 3-178.

6. Гечег Ф., О произведениях упорядоченных автоматов. I, Acta Sei. Math. 1963. V. 24, N 3-4. P. 244-250.

7. Глилг <f> f) ««rti^eo/itfwKffT un/yn tra/tv/su-u ui-v nЙ -mл илтлд tt Arfa К./Гckf-Vv 1 Qfiil \t« J- V "XV-JL "ЗГ « «I I Vf/ V WW U<a Will WhfJL W WV -VVIIII V WW WU II V\J VVU UI/VWVl ± ± J ¿JU^VHA- kw' . iviCLvii. -i. A ' T , ¿V,N 1-2. P. 124-128.

8. Глушков B.M., Абстрактная теория автоматов, Успехи мат. наук, 1961. Т. 16, N 5. С. 3-62.

9. Глушков В.М., Синтез цифровых автоматов. М., Наука, 1962.

10. К ад М.М., Об упорядочиваемости автоматов / / Упорядоченные множества и решетки. Саратов, 1995. Вып. И. С. 24-31.

11. Келли Дж.Л., Общая топология. М.: Наука, 1981.

12. Клиффорд А., Престон Г., Алгебраическая теория полугрупп. Т.1. М.: Мир, 1972.

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

14. Кудрявцев В.Б., Алешин С.В., Подколзин A.C., Введение в теорию автоматов. М.Потгт^р 1QRSLllU^AUi iWUV.

15. Мальцев А. И., Свободные топологические алгебры // Изв. АН СССР. Сер. мат. 1957. Т. 21. С. 171-198.

16. Молчанов В.А., О приложениях теории бинарных отношений в топологии// Теория полугрупп и ее приложения. Вып. 8. Саратов: Изд-во Сарат. гос. ун-та, 1987. С. 46-59.

17. Молчанов В.А., Регулярные пространства сходимости// Теория полугрупп и ее приложения. Вып. 9. Саратов: Изд-во Сарат. гос. ун-та, 1988. С. 41-49.

18. Молчанов В.А., О применении повторных нестандартных расширений в топологии

19. ГЧ»« .,„m„ TP qfs /ЮЙО\ 1 П «Л 71j j У-sül\J. iViCLJ. -m.J'jJIl, J. . »J и \ J } U. \J~X~~ I -L .

20. Молчанов В.А., Введение в нестандартный анализ// Учебное пособие. Саратов: Изд-во Сарат. гос. пед. ин-та, 1990.

21. Молчанов Щ. Pi. Непрерывные сходимости отображении I/ йзз вуз Мат 1993 N 3 С 59-67.

22. Молчанов В.А. О представлениях топологических алгебр преобразованиями // Успехи мат. наук. 1993. Т. 48. N 3 (291). С. 195-196.

23. Молчанов В.А., Нестандартные сходимости в пространствах отображений // Сибирский математический журнал,32, N 6. 1992. С. 141-153.

24. Молчанов В.А., Нестандартные многообразия псевдотопологических алгебраических систем j j Сибирский математический журнал, Т. 32 (1991), N 3, С. 104-112.

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

26. Протасов И. В., Многообразия топологических алгебр j j Сиб. мат. журн. 1984. Т. 25, N о. С. 125-134.

27. Салий В.Н., Универсальная алгебра и автоматы. Саратов, Изд-во СГУ. 1988.

28. Сперанский Д.В., Обощенные линейные автоматы без потери информации// Известия РАН. Теория и системы управления, 1997.

29. Спивак М.А., Введение в абстрактную теорию автоматов. Изд-во Сарат.ун- та, 1970.

30. Сытник А.А., ПеречЦ.слимостъ при восстановлении поведения автоматов// Доклады РАН, 1993, т. 238, с. 25-26.

31. Almeida J., On pseudovarieiies, varieties of languages, filters of congruences, pseudoidentities and related topics j j Algebra Universalis, 1990, V. 27. P. 333-350.

32. Arbib M., Tolerance automata //Kybernetika cislo, Rocnik. 1967. V.3. P. 223-233.

33. Ash C. J., Pseudovarieiies, generalized varieties and similary described classes // J. Algebra, 1985, V. 92. P. 104-115.

34. Birkhoff G., On the structure of abstract algebras)j Proc. Cambridge Phil. Soc. 1935. V. 31. P. 433-454.

35. Birkhoff G.j Lipson J.D. Universal algebra and automata //Proc. Tarski Symp. (Proc. Symp. Pure Math., V.25). V.2. Providence, R.I., 1974. - P.41-51.

36. Eilenberg S., Automata, languages and machines. Vol.B. Academic Press, New York, San Francisco, London, 1976.

37. Eilenberg S., Schttzenberger M.P., On pseudovarieiies of monoids // Advances in Math. 1976. V. 19. N 3. P. 413-448.

38. Lallement G., Semigroups and combinatorial applications. Wiley-Interscience Publication. John Wiley Sons. New York, Chichester. Brisbane. Toronto. 1979.

39. Molchanov V.A., Nonstandard characterization of pseudovarieiies and its applications to the theory of finite semigroups// Summaries of talks, Conference on Semigroup Theory and its Applications in memory of Alfred H.Clifford. New Orleans. 1994. P. 2.

40. Molchanov "V' \ ^loTisi&Tvdcivd chctTQctsTizcit'iOTir of pscttdovctTtctics j j A-I^cfers. XJiiivcrss.lis> 33 (1995) 533-547.

41. Molchanov V.A., Nonstandard congruences and lattices of pseudovarieties, Semigroups, automata and languages. (J. Almeida, Ed.) Wold Scientific, Singapore-New Jersey-London. 1996. P. 183-193.

42. Reiterman J., The Birkhoff theorem for finite algebras // Algebra Universalis, 1982, V. 14. P. 1-10,

43. Robinson, A. Nonstandard Analysis. Studies in Logic and the Foundations of Mathematics, North-Holland, 1966.

44. Simovici Dan A., On the theory of reduction of semilatticial automata j j An. Sti. ale Univ. "Al.l.Cuza" Din lasi. (Ser. Noua). Sec. la. 1976. V. 22. 1. P. 107-110.

45. Tarski A., Contributions to the theory of models. III./j Proc. Koninkl. Nederl. Acad. Wetensch. 1955. ASS: 1. P. 56-64.

46. Taylor W., Varieties of topological algebras // J. Austral. Math. Soc. 1977. V. 23A, N 2. P. 207-241.

47. Therien D., Classification of regular languages by congruences j j Ph.D. thesis. University of Waterloo, 1980.