Введение к работе
Актуальность темы. Теория автоматов представляет собой один из основных разделов математической кибернетики. Главным объектом изучения этой теории является устройство, предназначенное для преобразования информации. Такие устройства естественным образом возникают в многочисленных задачах, связанных с вычислительной техникой и управлением, в задачах теории связи и многих других [1]. В общем случае, устройство преобразования информации может находиться в различных состояниях, которые изменяются под влиянием определенных внешних воздействий (входных сигналов) и, в свою очередь, сами воздействуют на внешнюю среду (с помощью выходных сигналов). Математической моделью такого устройства является особая многоосновная система Л — {X, У, S, 5, А), называемая автоматом. Три основных множества X, Y, S называются соответственно множеством входных сигналов, множеством выходных сигналов и множеством состояний автомата. Бинарные операции 5 : S х X —> S и A : S х X -> Y называются функцией переходов и выходной функцией соответственно.
В теории автоматов и ее приложениях, наряду с классическим понятием автомата, у которого основные множества X, К, S являются аморфными конечными множествами, рассматриваются также автоматы, у которых множества состояний, входных и выходных сигналов наделены дополнительной математической структурой, сохраняющейся функциями <5 и А. В качестве таких дополнительных структур могут выступать, например, алгебраические структуры конечного поля или линейного пространства, реляционные структуры упорядоченного множества или толерантного пространства, топологические структуры топологического пространства или топологического векторного пространства и т.д. Автоматы, наделенные такими дополнительными структурами, называются, соответственно, автоматами над конечными полями, линейными автоматами, упорядоченными автоматами, толерантными автоматами, топологическими автоматами и топологически-
ми линейными автоматами. Исследованиям таких автоматов посвящены, например, работы Сперанского Д.В. и Сытни-ка А.А., Плоткина Б.И. и Филькенштейна М.Я., Гечега Ф. и Каца М.М., Арбиба М. и многих других. В общем случае автоматы, основные множества которых наделены дополнительной математической структурой, называются структуризован-ными автоматами. Многочисленные исследования в этом направлении характеризуются широким использованием алгебраических средств, и, таким образом, автомат - один из основных объектов математической кибернетики - становится предметом научного интереса алгебраической теории автоматов, которая непосредственно связана с важными разделами универсальной алгебры [2] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, к вопросам их декомпозиции и классификации, к теории языков и алгоритмов. В настоящей работе продолжается изучение структуризо-ванных автоматов, основные множества которых наделены как алгебраической, так и топологической структурами. Целью диссертационной работы является исследование категорий топологических алгебраических автоматов с целью разработки техники построения универсальных объектов таких категорий. Особый интерес к этой тематике объясняется тем, что понятие универсального объекта играет центральную роль в многочисленных приложениях теории категорий к теории автомагов, поскольку оно отражает принципиально важные свойства изучаемых автоматов. Например, минимальные автоматы являются универсальными притягивающими объектами в категориях эквивалентных автоматов, которые полностью определяют функции экспериментов таких автоматов. С другой стороны, свободные автоматы являются универсальными отталкивающими объектами в категориях автоматов, замкнутых относительно формирования гомоморфных образов, подсистем и прямых произведений (называемых кратко HSP-замкнутыми категориями или многообразиями), которые характеризуют элементарные свойства таких автоматов, выражающиеся тождествами языка логики узкого исчисления предикатов (УИП). В результате построение свободных автоматов является осно-
вой реализации важнейшей концепции в изучении категорий автоматов, которая (в форме известной теоремы Биркгофа) отражает тесную взаимосвязь семантического подхода к изучению HSP-замкнутых классов автоматов и синтаксического подхода к изучению классов автоматов, определяемых множествами тождеств. Показательно, что перенос такого двойственного подхода к изучению автоматов на случай категорий конечных автоматов, замкнутых относительно формирования подсистем, гомоморфных образов и конечных прямых произведений (называемых кратко НЗРдп-замкпутыми категориями или псевдомногообразиями), представляет особый интерес не только для теории автоматов, но и для такого важнейшего направления компьютерной науки, как теория распознаваемых языков, поскольку известное соответствие Эйленберга [3] устанавливает тесную взаимосвязь между многообразиями распознаваемых языков и псевдомногообразиями соответствующих алгебр. Хорошо известно, что такие категории в общем случае не имеют универсальных отталкивающих объектов, и поэтому в теории псевдомногообразий возникает важнейшая задача построения аналогов таких универсальных объектов вне рассматриваемых категорий. Разнообразные подходы к решению этой актуальной проблемы были разработаны Тьереном Д., Эйленбергом С и Шютценберже М.П., Ашем К.Дж., Рейтер-маком Дж., Алмейдой Дж. и другими. Унифицированный подход к теории топологических алгебраических систем и к теории псевдомногообразий разработал Молчанов В.А. на основе методов нестандартного анализа [4]. Распространение в настоящей работе этого нестандартного подхода на топологические алгебраические автоматы позволяет сводить упомянутую выше проблематику теории таких автоматов к вопросам теории нестандартных многообразий топологических алгебраических автоматов и эффективно проводить исследования в этом направлении логико-алгебраическими методами нестандартного анализа.
Цель работы. Разработать нестандартные методы построения универсальных объектов в категориях структуризо-ванных автоматов и с их помощью решить следующие задачи:
- исследовать вопрос о существовании минимального авто
мата в классе эквивалентных топологических алгебраических
автоматов;
- исследовать вопрос о существовании универсального
функтора представления категорий в категориях топологичес
ких алгебраических автоматов;
доказать существование автомата, порожденного топологическими пространствами и нестандартными определяющими (алгебраическими ж топологическими) соотношениями в SPI-замкнутой категории топологических алгебраических автоматов;
обобщить известную теорему Биркгофа о структурной ха-рактеризации многообразий алгебраических автоматов на случай нестандартных многообразий топологических алгебраических автоматов;
обобщить нестандартный подход к теории псевдомногообразий конечных алгебр на случай псевдомногообразий конечных алгебраических автоматов;
изучить решетку псевдомногообразий конечных алгебраических автоматов.
Методы исследования. В работе используются известные методы алгебраической теории автоматов, универсальной алгебры и нестандартного анализа.
Научная новизна. В диссертации разработаны методы построения универсальных объектов в категориях структури-зованных автоматов и изучены приложения этих объектов к вопросам минимизации структуризованных автоматов и харак-теризации некоторых важных классов таких автоматов.
Основные результаты диссертации:
- получена нестандартная конструкция минимального авто
мата в классе эквивалентных топологических алгебраических
автоматов;
доказано существование универсального функтора представлений категорий в SPI-замкнутых категориях топологических алгебраических автоматов;
доказано существование топологического алгебраического автомата, порожденного топологическими пространства-
ми и нестандартными определяющими соотношениями в SPI-замкнутой категории топологических алгебраических автоматов;
- найдена структурная характеристика нестандартных
многообразий топологических алгебраических автоматов;
получена нестандартная характеристика псевдомногообразий конечньгх алгебраических автоматов;
описана решетка псевдомногообразий конечных алгебраических автоматов.
Все перечисленные результаты являются новыми.
Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в дальнейших исследованиях по теории автоматов и универсальной алгебре.
Апробация работы- Результаты диссертации докладывались на Международной конференции по средствам математического моделирования "MATHTOOLS'97" (Санкт-Петербург, 1997), на Международной алгебраической конференции памяти А.Г. Куроша (Москва, 1998), на региональной конференции "МиН-XXI" (Саратов, 1998), на Международном семинаре, посвященном памяти проф. Л.А. Скорнякова (Волгоград, 1999), на Международной конференции по общей алгебре "ААА60" (Дрезден, Германия, 2000), на Международной конференции по теории полугрупп (Сегед, Венгрия, 2000), на заседаниях алгебраического семинара в педагогическом институте Саратовского государственного университета (1997-2000) и объединенного семинара кафедр математической кибернетики и теоретических основ информатики в Саратовском государственном университете (2000).
Диссертация выполнена в рамках научно-исследовательской темы Министерства образования РФ "Нестандартная теория топологических моделей и распознаваемых языков" и проекта ИНТАС " Комбинаторная и геометрическая теории групп и полугрупп и их приложения к компьютерной науке", грант 99-1224.
Публикации. Основные результаты диссертации опубликованы в работах [Al] - [АН].
Объем работы. Диссертация состоит из введения, четырех глав и списка литературы из 47 наименований. Общий объем диссертации 86 страниц.