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

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н.Г. ЧЕРНЫШЕВСКОГО

■ - м 1 ; . . ; -1

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

ОТРЫВАНКИНА Татьяна Михайловна

УНИВЕРСАЛЬНЫЕ ОБЪЕКТЫ В КАТЕГОРИЯХ СТРУКТУРИЗОВАННЫХ АВТОМАТОВ

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

Автореферат

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

Саратов - 2000

Работа выполнена на кафедре прикладной математики Саратовского государственного университета.

Научный руководитель:

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

Официальные оппоненты:

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

Ведущая организация:

Новосибирский государственный технический университет

Защита состоится "/Ц" г. в Т^Гчас. ^мин.

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

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

Автореферат разослан " & " Щ^М^гД 2000 г.

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

П.Ф.Недорезов

4 М. 0

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

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

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

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

В настоящей работе продолжается изучение структуризо-ванных автоматов, основные множества которых наделены как алгебраической, так и топологической структурами. Целью диссертационной работы является исследование категорий топологических алгебраических автоматов с целью разработки техники построения универсальных объектов таких категорий. Особый интерес к этой тематике объясняется тем, что понятие универсального объекта играет центральную роль в многочисленных приложениях теории категорий к теории автоматов, поскольку оно отражает принципиально важные свойства изучаемых автоматов. Например, минимальные автоматы являются универсальными притягивающими объектами в категориях эквивалентных автоматов, которые полностью определяют функции экспериментов таких автоматов. С другой стороны, свободные автоматы являются универсальными отталкивающими объектами в категориях автоматов, замкнутых относительно формирования гомоморфных образов, подсистем и прямых произведений (называемых кратко HSP-замкнутыми категориями или многообразиями), которые характеризуют элементарные свойства таких автоматов, выражающиеся тождествами языка логики узкого исчисления предикатов (УИП). В результате построение свободных автоматов является осно-

вой реализации важнейшей концепции в изучении категорий автоматов, которая (в форме известной теоремы Биркгофа) отражает тесную взаимосвязь семантического подхода к изучению НЭР-замкнутых классов автоматов и синтаксического подхода к изучению классов автоматов, определяемых множествами тождеств. Показательно, что перенос такого двойственного подхода к изучению автоматов на случай категорий конечных автоматов, замкнутых относительно формирования подсистем, гомоморфных образов и конечных прямых произведений (называемых кратко Н Э Ррш - замкнутым и категориями или псевдомногообразиями), представляет особый интерес не только для теории автоматов, но и для такого важнейшего направления компьютерной науки, как теория распознаваемых языков, поскольку известное соответствие Эйленберга [3] устанавливает тесную взаимосвязь между многообразиями распознаваемых языков и псевдомногообразиями соответствующих алгебр. Хорошо известно, что такие категории в общем случае не имеют универсальных отталкивающих объектов, и поэтому в теории псевдомногообразий возникает важнейшая задача построения аналогов таких универсальных объектов вне рассматриваемых категорий. Разнообразные подходы к решению этой актуальной проблемы были разработаны Тьереном Д., Эйленбергом С. и Шютценберже М.П., Ашем К.Дж., Рейтер-маном Дж., Алмейдой Дж. и другими. Унифицированный подход к теории топологических алгебраических систем и к теории псевдомногообразий разработал Молчанов В.А. на основе методов нестандартного анализа [4]. Распространение в настоящей работе этого нестандартного подхода на топологические алгебраические автоматы позволяет сводить упомянутую выше проблематику теории таких автоматов к вопросам теории нестандартных многообразий топологических алгебраических автоматов и эффективно проводить исследования в этом направлении логико-алгебраическими методами нестандартного анализа.

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

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

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

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

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

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

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

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

Научная новизна. В диссертации разработаны методы построения универсальных объектов в категориях структури-зованных автоматов и изучены приложения этих объектов к вопросам минимизации структуризованных автоматов и харак-теризации некоторых важных классов таких автоматов.

Основные результаты диссертации:

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

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

- доказано существование топологического алгебраического автомата, порожденного топологическими пространства-

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

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

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

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

Все перечисленные результаты являются новыми.

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

Апробация работы- Результаты диссертации докладывались на Международной конференции по средствам математического моделирования "MATHTOOLS'97" (Санкт-Петербург, 1997), на Международной алгебраической конференции памяти А.Г. Куроша (Москва, 1998), на региональной конференции "МиН-XXI" (Саратов, 1998), на Международном семинаре, посвященном памяти проф. J1.A. Скорнякова (Волгоград, 1999), на Международной конференции по общей алгебре "ААА60" (Дрезден, Германия, 2000), на Международной конференции по теории полугрупп (Сегед, Венгрия, 2000), на заседаниях алгебраического семинара в педагогическом институте Саратовского государственного университета (1997-2000) и объединенного семинара кафедр математической кибернетики и теоретических основ информатики в Саратовском государственном университете (2000).

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

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

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

Содержание работы

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

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

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

Классы струхтуризовалных автоматов с отображениями, сохраняющими их алгебраическую и топологическую структуры, образуют категории.

В общем случае категория К представляет собой класс объектов, обозначаемый ОЬ К, вместе с классом морфиз-мов, обозначаемым Мог К, которые удовлетворяют следующим свойствам:

1) каждой упорядоченной паре объектов (а, Ь) сопоставлено множество морфизмов Мог(а,6), так что класс Мог К является объединением попарно не пересекающихся множеств Мог(а, 6);

2) для любых морфизмов а 6 Мог(а,Ь), /3 € Мог(6, с) существует единственный элемент множества Мог(а, с), называемый композицией или произведением морфизмов а, (5 и обозначаемый через а/3;

3) композиция морфизмов ассоциативна, т.е. для морфиз-мов а € Мог(а, &), ¡3 £ Мог(6, с), 7 6 Мог(с, d) выполняется равенство: (а/?)7 = а(/37);

4) каждому объекту а сопоставлен такой морфизм £а S Мог(а,а), что для любых а (Е Мог(Ь, а) и (3 € Мог(а, с) выполняются равенства аеа = a, eaj3 =

Объект Л категории К называется универсальным отталкивающим объектом в К, если для любого объекта В из К имеется единственный морфизм / : А —» В. Двойственным образом, А - универсальный притягивающий объект, в К, если для каждого В G Ob К имеется единственный морфизм / : В -> Л.

Категория К называется Ы-замкнутой (соответственно, I-замкнутой), если она замкнута относительно формирования непрерывных гомоморфных (топологических изоморфных) образов, S-замкнутой (соответственно, S-замкнутой), если она замкнута относительно формирования (замкнутых) подобъ-ектов, Р-замкнутой (соответственно, Рдп-замкнутой), если она замкнута относительно формирования (конечных) прямых произведений, и Pow-замкнутой, если она замкнута относительно формирования прямых степеней.

При исследовании категорий структуризованных автоматов в работе широко используются методы нестандартного анализа из [4]. С целью упрощения применения этих методов можно считать, что основные множества всех изучаемых математических структур являются подмножествами множества индивидов S стандартного теоретико-множественного универсума U. Главная идея нестандартного анализа заключается в построении отображения * стандартного универсума U в собственную подструктуру *U нового теоретико-множественного универсума Uj с расширенным множеством индивидов *S, для которого выполняются описанные в [4] принципы нестандартного анализа. В результате каждое множество А € U расширяется до множества * А Е *U и по принципу переноса для любых Ах,..., Ап G U и любой формулы с ограниченными кванторами языка узкого исчисления предикатов <fi(xi...,xn) предложение ф{Ах: ...,Ап) истинно в U в том и только том случае,

если предложение ф{* А\,..., *Ап) истинно в *и. Структура *и с основными теоретико-множественными операциями и отношениями называется нестандартным универсумом. Множество А называется внутренним, если А Е *и, и стандартным, если А = * В для некоторого ВеТ1.

При нестандартном подходе открытая топология т на множестве А определяется соответствием а С А х * А со значениями а(а) = : а € X € т} (а 6 А). Такие соответствия называются (нестандартными) топологиями и на них распространяется общепринятая топологическая терминология.

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

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

Пусть О - произвольная алгебрическая сигнатура, которая представлена в виде суммы множеств + где VI р и Пр - множества функциональных и предикатных символов сигнатуры соответственно и К - категория топологических алгебраических П-систем с непрерывными гомоморфизмами.

Топологическим алгебраическим автоматом над категорией К (сокращенно К-автоматом) называется многоосновная алгебраическая система вида А = (X, У, Б, <5, А), где топологические алгебраические системы X — (Х,П,р), У — (У, П, а), Б = (Б, £1, а) являются объектами категории К и отображения 6 : Б х X ~> Б, X : Б х X —> У - морфизмами категории К.

Непрерывным гомоморфизмом по состояниям (или просто гомоморфизмом) К-автомата А = (X, У, Б, 6, А) в К-автомат А\ = (АГ, У, ¿1, Ах) называется непрерывный гомоморфизм ф : Б —> Б\, удовлетворяющий для любых в 6 Б,х 6 X соотношениям: ф(6(з, х)) = 5х(с£>(з), х), А(з,ж) — Ах(0(з), х).

Класс К-автоматов с такими гомоморфизмами образует категорию Ак-

В К-автомате А = {Х,У, Б, <5, А) для любого х € X определяются непрерывные гомоморфизмы 6Х : Б —» Б и Хх : Б У

по формулам: ^(э) = ¿(5,2;), Лг(5) = \{в,х) (я € 5). Наряду с указанными гомоморфизмами для любого я € Б рассмотрим функцию экспериментов А3 : Ж —> К, значение которой для слова V) = х\ .. .хп над алфавитом X определяется формулой А„(и)) = ЛТпо5Хп_1о.. .о^о^Дз). Множество всех отображений вида А; (я € 5) будем называть классом функций экспериментов автомата А и обозначать символом Ед.

Автоматы А и В называются эквивалентными, если ^д — Рц, т.е. соответствующие этим автоматам классы функций экспериментов , совпадают.

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

Теорема 1. Пусть К - категория топологических алгебраических П-систем, замкнутая относительно формирования прямых степеней и замкнутых подсистем, А - произвольный К-автомат и Ь — класс всех К-автоматов, эквивалентных автомату А. Тогда в классе Ь существует единственный с точностью до топологического изоморфизма К-автомат А г,, который удовлетворяет следующим условиям:

1) для любого автомата А из класса Ь существует гомоморфизм А на автомат Ас,

2) все состояния автомата Апопарно не эквивалентны;

3) мощность множества состояний автомата Аь не превосходит мощности множества состояний любого автомата из класса Ь.

Такой автомат Аь является универсальным притягивающим объектом в подкатегории Ь категории А^ и называется минимальным К-автоматом класса Ь.

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

без предикатных символов. В разделе 3.1 исследуется важный вопрос о существовании универсального функтора для представлений категорий в категориях топологических алгебраических автоматов. Приводятся условия существования в таких категориях автоматов, определяющихся топологическими пространствами и классами нестандартных определяющих соотношений. В разделе 3.2 для описания свойств топологических алгебраических автоматов вводится нестандартный формальный язык УИП и определяется его интерпретация. Здесь же получена структурная характеристика нестандартных многообразий топологических алгебраических автоматов, являющаяся обобщением известной теоремы Биркгофа о многообразиях алгебраических автоматов [5, теорема 12.1], и найдены структурные характеристики многообразий топологических алгебраических автоматов, аксиоматизируемых стандартными, полустандартными или топологическими тождествами.

Пусть М - категория упорядоченных пар топологических пространств с парами непрерывных отображений в качестве морфизмов и А - регулярная категория полугрупповых топологических алгебраических автоматов (без выхода) с непрерывными гомоморфизмами. Рассмотрим такое представление О категории М в категории А, что для пары (X, 2) 6 ОЬ М и автомата Л = (Г\д, 5д, <5) из класса ОЬ А множество С((Х, 2), Л) состоит из некоторых упорядоченных пар непрерывных отображений X в Гл и ¿"в 5а- При этом считаем, что представление С резидуально [2] и для любой пары непрерывных отображений (<р1,(р2) € С((Х, и топологически порожденного парой множеств (срх(Х),<рподавтомата В автомата Л пара отображений (Их, /12), где = 1рв о /г2 = /5В ° ^ принадлежит множеству С((Х, '¿),Б). При сделанных предположениях справедлив следующий результат.

Теорема 2. Если категория автоматов А содержит автомат с одноэлементной ^-алгеброй в качестве множества состояний и замкнута относительно формирования топологических изоморфизмов, прямых произведений и замкнутых подсистем, то представление б обладает универсальным функтором.

Построенный в ходе доказательства для упорядоченной па-

ры топологических пространств (X, Z) топологический алгебраический автомат 14(Х, Я) является универсальным отталкивающим объектом в подкатегории категории А, определяемой объектами Л € ОЬА, для которых С((Х, Я),Л) ф 0.

Из теоремы 2 следует решение вопроса о существовании автомата, порожденного в ЭРГ-замкнутой категории А парой топологических пространств и нестандартными определяющими соотношениями.

Для описания классов топологических алгебраических автоматов по аналогии с [6] вводится нестандартный язык УИП С с двухсортным алфавитом, состоящим из множеств X н Z. Элементы нестандартных расширений *Х и *Z мы называем нестандартными переменными языка С (первого и второго сорта соответственно). Под нестандартными термами языка С (первого и второго сорта соответственно) понимаются элементы нестандартных расширений *\¥{Х) и где \У{Х) - свободная полугруппа слов над X и - П'-

алгебра ГУ-слов над Z для сигнатуры П' = У IV(X). Равенства ¿1 = ¿о, где ¿1, ¿2 ~ нестандартные термы одного и того же (первого или второго) сорта, называются нестандартными тождествами (первого или второго сорта соответственно).

Интерпретация нестандартных тождеств языка С в топологическом алгебраическом автомате Л = (Г, 5', 5) определяется с помощью отображений в\ : X —> Г, 6>2 '• £ —> Я, которые канонически расширяются до гомоморфизмов *9\ : * \У(Х) —> Т, *02 : и отображений вг : *\¥(Х) Г,

в2 : 5, где 01 = р-1 о *в1 и в2 = а"1 о *02 для

нестандартных топологий р и а на множествах Г и 5 соответственно. Мы говорим, что нестандартное тождество г-го сорта ¿1 = ¿2 выполняется в данной интерпретации, если = («' = 1,2).

Класс топологических алгебраических автоматов А называется нестандартным многообразием, если он аксиоматизируется некоторым классом нестандартных тождеств.

Основным результатом раздела 3.2 является следующая модификация известной теоремы Биркгофа.

Теорема 3. Класс топологических алгебраических автоматов

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

В четвертой главе исследуются классы конечных алгебраических автоматов. С целью упрощения изложения полученные результаты приводятся для случая автоматов без выхода и алгебраической сигнатуры Г2 без предикатных символов. В разделе 4.1 предлагается подход к характеризации псевдомногообразий таких автоматов посредством тождеств нестандартного языка УИП. Этот подход базируется на принципах нестандартного анализа и результатах работы [7]. В разделе 4.2 описана решетка псевдомногообразий конечных алгебраических автоматов.

По аналогии с [7] для характеризации классов конечных алгебраических автоматов используется описанный выше нестандартный язык УИП £ с двухсортным алфавитом, состоящим из счетных множеств X и Z. В этом случае при интерпретации языка С в конечном алгебраическом автомате А = (Г, 5,5) отображения^! : X -> Г и 02 : 2 —> 5, интерпретирующие переменные языка канонически расширяются до гомоморфизмов : *\¥(Х) -> Г и *92 : *Иго.>{%) 5, с помощью которых определяется выполнимость нестандартных тождеств в конечном алгебраическом автомате А-

Класс конечных алгебраических автоматов А называется нестандартным многообразием, если он аксиоматизируется классом нестандартных тождеств.

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

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

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

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

[1] Кудрявцев В.Б., Алешин C.B., Подколзин A.C., Введение в теорию автоматов. - М., Наука, 1985.

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

[3] Eilenberg S., Automata, languages and machines. Vol.B. -Academic Press, New York, San Francisco, London, 1976.

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

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

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

[7] Molchanov V.A., Nonstandard characterization of pseudovaríeties Ц Algebra Universalis, 33 (1995) 533-547.

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

[Al] Otryvankina Т.М., On minimization of structure automata // Международная конференция "MATHTOOLS'97: Tools for mathematical modelling", Тезисы докладов. Санкт-Петербург, 1997. С. 50-51.

[A2J Отрыванкина T.M., О минимизации структурных автоматов // Труды международной конференции "MATHTOOLS'97". Санкт-Петербург, 1998. С. 193-203.

[A3] Отрыванкина Т.М., О минимизации топологических структурных автоматов // Тезисы докладов региональной конференции "МиН-ХХП. Саратов: СГУ, 1998. С. 62-63.

[А4] Otryvankina T.M., On minimization of topological structure automata // Тезисы докладов, представленных на Международную алгебраическую конференцию памяти А.Г. Куроша. М: МГУ, 1998. С. 98.

[А5] Отрыванкина Т.М., О минимизации топологических алгебраических автоматов // Теоретические проблемы информатики и ее приложений. Саратов: ГосУНЦ "Колледж", 1998. Вып.2. С.85-89.

[А6] Отрыванкина Т.М., О минимизации топологических структурных автоматов (/ Пед. ин-т Саратов, гос. ун-та. Саратов, 1998. Деп. в ВИНИТИ 04.06.98, 1720-В98. 20 с.

[А7] Отрыванкина Т.М., Нестандартные многообразия топологических алгебраических автоматов // Тезисы докладов международного семинара, посвященного памяти проф. JI.A. Скорнякова. Волгоград, 1999. С. 50-51.

[А8] Otryvankina Т.М., On pseudovarieties of finite algebraic automata // Тезисы докладов Международной конференции "Логика и приложения", Новосибирск, 2000- С. 135.

[А9] Otryvankina Т.М., Nonstandard varieties of topological algebraic automata // Summaries of talks, International Conference on General Algebra "AAA60", Dresden, 2000. P. 22.

[A10] Otryvankina T.M., Lattice of pseudovarieties of finite algebraic automata // Summaries of talks, International Conference "Colloquium on semigroups". Seged, 2000. P. 20-21.

[All] Отрыванкина T.M., Нестандартные многообразия топологических алгебраических автоматов // Универсальная алгебра и ее приложения: Тр. междунар. семинара. Волгоград: Перемена, 2000. С. 232-237.

Подписано в печать 10.11.2000. Объем 1 п.л. Тираж 100 экз. Заказ 17. Отпечатано с оригинал-макета у ЧП "Бондарь НК". Свидетельство № 1719.

Введение.

Глава 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- ^ Л^иЛи/ домногообразий конечных алгебраических автоматов;

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

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

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

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.