Введение к работе
Актуальность темы. Работа посвящена развитию алгебраической теории упорядоченных автоматов. Главным объектом изучения является конечный детерминированный автомат без выхода, в общем случае частичный. Такой автомат определяется как тройка Л — {S,X,S), где S и X - произвольные конечные непустые множества, называемые соответственно множеством состояний и множеством входных сигналов автомата, а 5 С (5 х X) х S - однозначное бинарное отношение между множествами S х X и S (функция переходов автомата, в общем случае частичная). Заметим, что в алгебраической теории автоматов автомат Л трактуется как (частичная) унарная алгебра, что позволяет применить здесь хорошо разработанные унпверсальпо-алгебраичеекпе средства, придать установленным с их помощью фактам естественную автоматную трактовку.
Под упорядоченным автоматом понимается автомат А, на множестве состояпий которого задано некоторое нетривиальное отношение (частичного) порядка и>, устойчивое относительно функции переходов этого автомата. Тенденция в абстрактной теории автоматов, состоящая в том, чтобы вводить в множество состояппй автомата некоторую алгебраическую структуру (отношения, топологию л др.) и рассматривать те пли иные специальные виды функций переходов (монотонные, непрерывные и т.п.), была подмечена В.М.Глушковым еще в самом па-чале 60-х годов (см. [6, с.60]). К настоящему времени это направление получило значительное развитие . В наиболее общем виде такие автоматы изучались в работах Л.А.Скорнякова, Б.И.Плоткпна и др.
Примерами устойчивых в автомате Л бинарных отношений, теория которых к настоящему временп получила наибольшее развитие, могут служить конгруэнции, эндоморфизмы и автоморфизмы автомата.
Совокупность конгруэнции автомата Л образует решетку Соіь4. Алгоритм построения решетки СопД предложил Фарр [21]. Маккензи установлено, что для всякого-вполне определенного автомата существует вполне определенный автомат с четырьмя входными сигналами, имеющий такую же решетку конгруэнции (см. [14, с.42]). С.Р.Когаповский и В.В.Солдатова [9] доказали, что всякая конечная решетка представп-ма как решетка конгруэнции частичного автомата с двумя входными сигналами. Вполне определенные автономные автоматы с различными типами решетки конгруэпций изучались в работах Л.А.Скорнякова, Д.П.Егоровой, Йоэли, Бермапа и др.
Эндоморфизмы автомата Л образуют полугруппу ЕпсІД, а автоморфизмы — группу AutA Алгоритмы вычисления полугруппы ЕпсІЛ предложили Гржнмала-Буссе [22] и В.Н.Салпй [14]. Группа автоморфизмов вполне определенного автономного автомата описана В.З.Фейнбергом [18]. В ряде работ Варле, Л.А.Скорнякова и А.М.Бочкпна получено описанпе вполне определенных автономных автоматов с различными типами полугрупп эндоморфизмов.
Автоматы, наделенные устойчивым отношением толерантностп, изучали Арбпб [20] (в связи с приложениями в распознавании образов), И.П.Ильичева, В.В.Печеыкин [8] (в связи с приложениями в технической диагностике) и др.
В математической кибернетике многочисленные приложения находят отношения порядка. Отметим, например, теорию игр с упорядоченными исходами В.В.Розена (см. [12]), теорию упорядоченных систем В.А.Горбатова [7], дискретное программирование над линейно упорядоченными коммутативными полугруппами (см. обзор Е.Я.Габовпча [3]) и др. В ряде работ рассматривались и упорядоченные автоматы (у-автоматы). В работах Гечега [4}т [5]' описаны у-автоматы (с выходом), вложпмые в произведение у-автоматов и представимые в виде такого произведения. В книге Г.П.Агибалова [1] развивается теория автоматов (с выходом) на полурешетках. Такие автоматы являются функциональными моделями цифровых устройств, описывающими поведение устройств не только в статике - при фиксированном входном сигнале, но и в динамике - при смене входного сигнала. Задача редукции для пс>-лурешеточно упорядоченных автоматов (с выходом) решается в работе Симовичи [24]. Лустпг [23] изучал задачу о том, когда все изотопные отображения одного вполне определенного автономного у-автомата в другой такой же автомат являются, гомоморфизмами автоматов. Г. Ру-банович [13] получил описанпе вполне определенных автономных автоматов, которые можно линейно упохжнрчить (в последних двух работах использовался язык унарных алгебр).
Несмотря на указанные работы, общая теория упорядоченных автоматов пока развита в недостаточной степени. Оставались неисследованными также задачи характеризаппи автоматов, которые можно нетривиально упорядочить, и автоматов, которые можно линейно упорядочить.
Цель работы. Развить основы теории упорядоченных автоматов. Исследовать вопросы упорядочиваемостп и линейной упорядочи-ваемости произвольных автоматов1. Исследовать задачи доопределения частичных упорядоченных и линейно упорядоченных автоматов.
Научная новизна. В работе для автоматов бет выхода получены следующие основные результаты:
получен критерий нетривиальной упорядочиваемости автомата;
получен критерий линейной упорядочиваемости автомата;
решены задачи описания частичных упорядоченных и линейно упорядоченных автоматов, допускающих доопределение;
- оппсаны упорядочиваемые автоматы, не имеющие собственных
упорядочиваемых подавтоматов.
Все перечисленные результаты являются новыми.
Теоретическая и прикладная ценность. Работа имеет теоретический характер, ее результаты могут быть использованы в дальнейших научных теоретических исследованиях - в алгебраической теории автоматов, универсальной алгебре п теории упорядоченных множеств, а также в приложениях теории автоматов, в математической кибернетике и в информатике.
Апробация работы. Результаты диссертации докладывались на X Международной конференции по проблемам теоретической кибернетики (Саратов, 1993), на XI Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996). на заседаниях Саратовского городского алгебраического семинара (1993 - 1995) и семинара по математической кибернетике при Саратовском университете (1993 - 1996), на итоговой научной конференции механико-математического факультета и ВЦ СГУ (1995).
Публикации. Основные результаты диссертации опубликованы в работах [А1] - [А6].
Объем работы. Работа ссх:топт из введения, двух глав, содержащих семь параграфов, и библиографии, включающей 77 наименований. Диссертация изложена на 104 страницах.