Упорядоченные автоматы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Й-.

с о САРАТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ пм. Н.Г.ЧЕРНЫШЕВСКОГО

о

Оо

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

КАЦ Михаил Матвеевич УПОРЯДОЧЕННЫЕ АВТОМАТЫ

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

АВТОРЕФЕРАТ диссертации на соисканпе ученой степени кандидата фшшко-математпческнх наук

САРАТОВ - 1997

Работа выполнена на кафедре математической кибернетики и компьютерных наук

Саратовского государственного университета им. Н.Г.Чернышевского

Научный руководитель - кандидат физико-математических наук,

профессор В.Н.САЛИЙ.

Официальные оппоненты - доктор физико-математических наук,

профессор В.В.РОЗЕН, кандидат физико-математических паук, доцент В.В.ПЕЧЕНКИН.

Ведущая организация - Научно-исследовательский институт

прикладной математики и кибернетики при Нижегородском государствепном университете им. Н.И.Лобачевского.

Защита состоится " 1в_ " ОКтЛ^рХ. 1997 г. в /■£"ч. З&мин. на заседании Диссертационного Совета К 063.74.04 по присуждению ученой степени кандидата наук в Саратовском государственном университете по адресу: 410026, г.Саратов, Астраханская, 83.

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

Автореферат разослан //" Л^рА

1997 г.

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

доцент П.Ф.НЕДОРЕЗОВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Работа посвяхцсна развитию алгебраической теории упорядоченных автоматов. Главным объектом изучения является конечный детерминированный автомат без выхода, в общем случае частичный. Такой автомат определяется как тройка Л — {Б,Х,5), где 5 п X - произвольные конечные непустые множества, называемые соответственно множеством состояний и множеством входных сигналов автомата, а 5 С (5 х X) х 5 - однозначное бинарное отношение между множествами 5 х X и й (функция переходов автомата, в общем случае частичная). Заметим, что в алгебраической теории автоматов автомат Л трактуется как (частичная) унарпая алгебра, что позволяет применить здесь хорошо разработанные унпверсальпо-алгебраическле средства, придать установленным с их помощью фактам естественную автоматную трактовку.

Под упорядоченным автоматом понимается автомат Л, на множестве состояний которого задано некоторое нетривиальное отношение (частичного) порядка и>, устойчивое относительно функции переходов этого автомата. Тенденция в абстрактной теории автоматов, состоящая в том, чтобы вводить в множество состояний автомата некоторую алгебраическую структуру (отношения, топологию л др.) п рассматривать те или иные специальные виды функций переходов (монотонные, непрерывные и т.п.), была подмечена В.М.Глушковым еще в самом па-чале 60-х годов (см. [6, с.60]). К настоящему времени это направление получпло значительное развитие . В наиболее общем виде такие автоматы изучались в работах Л.А.Скорнякова, Б.И.Плоткпна и др.

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

Совокупность конгруэнции автомата Л образует решетку Согь4. Алгоритм построения решетки СопД предложил Фарр [21]. Маккензи установлено, что для в сякого-вполне определенного автомата существует вполне определенный автомат с четырьмя входными сигналами, имеющий такую же решетку конгруэпцлй (см. [14, с.42]). С.Р.Когаловский и В.В.Солдатова [9] доказали, что всякая конечная решетка представп-ма как решетка конгруэнций частичного автомата с двумя входными сигналами. Вполне определенные автономные автоматы с различными тппамп решетки конгруэнции изучались б работах Л.А.Скорнякова, Д.П.Егоровой, Иоэли, Бермапа и др.

Эндоморфизмы автомата А образуют полугруппу Епс1Л, а автоморфизмы — группу Аи<;А Алгоритмы вычисления полугруппы Еп(1Л предложили Гржимала-Буссе [22] и В.Н.Салпй [14]. Группа автоморфизмов вполне определенного автономного автомата описана В.З.Фейнбергом [18]. В ряде работ Варле, Л.А.Скорнякова и

A.М.Бочкина получено описание вполне определенных автономных автоматов с различными типами полугрупп эндоморфизмов.

Автоматы, наделенные устойчивым отношением толерантности, изучали Арбпб [20] (в связи с приложениями в распознавании образов), И.П.Ильичева, В.В.Печешшп [8] (в связи с приложениями в технической диагностике) и др.

В математической кибернетике многочисленные приложения находят отношения порядка. Отметим, например, теорию игр с упорядоченными исходами В.В.Розена (см. [12]), теорию упорядоченных систем

B.А.Горбатова [7], дискретное программирование над линейно упорядоченными коммутативными полугруппами (см. обзор Е.Я.Габовпча [3]) и др. В ряде работ рассматривались и упорядоченные автоматы (у-автоматы). В работах Гечега [4}т [5]' описаны у-автоматы (с выходом), вложимые в произведение у-автоматов и представимые в виде такого произведения. В книге Г.П.Агибалова [1] развивается теория автоматов (с выходом) па полурешетках. Такие автоматы являются функциональными моделями цифровых устройств, описывающими поведение устройств не только в статике - при фиксированном входном сигнале, но и в динамике - при смене входного сигнала. Задача редукции для по-лурешеточно упорядоченных автоматов (с выходом) решается в ¡заботе Симовичи [24]. Лустнг [23] изучал задачу о том, когда все изотопные отображения одного вполне определенного автономного у-автомата в другой такой же автомат являются, гомоморфизмами автоматов. Г. Ру-банович [13] получил описание вполне определенных автономных автоматов, которые можно линейно упох>адочить (в последних двух работах использовался язык унарных алгебр).

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

Цель работы. Развить основы теории упорядоченных автоматов. Исследовать вопросы упорядочиваемостп и линейной упорядочи-ваемости произвольных автоматов-. Исследовать задачи доопределения частичных упорядоченных и линейно упорядоченных автоматов.

Научная новизна. В работе для автоматов бет выхода получены следующие основные результаты:

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

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

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

- описаны упорядочиваемые автоматы, не имеющие собственных упорядочиваемых подавтоматов.

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

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

Апробация работы. Результаты диссертации докладывались на X Международной конференции по проблемам теоретической кибернетики (Саратов, 1993), на XI Международной конференции по проблемам теоретической кибернетики (Ульяновск, 1996). на заседаниях Саратовского городского алгебраического семинара (1993 - 1995) и семинара по математической кибернетике при Саратовском университете (191)3 - 1996), на итоговой научной конференции механико-математического факультета и ВЦ СГУ (1995).

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

Объем работы. Работа состоит из введения, двух глав, содержащих семь параграфов, и библиографии, включающей 77 наименований. Диссертация изложена на 104 страницах.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Пусть А = (Б, X, 5) - произвольный автомат. Если первая проекция рг\& отношения 5 совпадает с множеством 5' х X, то автомат А называется вполне определенным, а отношение 5 рассматривается как отображение, т.е. 8: Я х X —► Л'; если рг 1Л ф Вх , то автомат А называется частичным. Автомат А = (3, X, 5) называется автономным, если X является одноэлементным множеством. В дальнейшем автономные автоматы будем записывать в виде А — (5,5) и рассматривать 8 как однозначное бинарное отношение в множестве 5, т.е. 5 С 5 х 5. Если автономный автомат А = (5. <5) является вполне определенным [частичным] , то <5 можно рассматривать как полное [частичное] преобразование множества 5, т.е. 5:5 —* 5.

Пусть А = (5, X, 8) - произвольный автомат. Для фиксированного входного сигнала х € X определим однозначное бппарное отношение 8Х в множестве 5, положив 8Х := {(.91, в2) £ 5x5: , х), з2) Е 5} (символ ":=" означает равенство по определению).

Автономные автоматы А.г = (3Г8Х), х € X, называются автономными компонентами автомата А.

Бинарное отношение р С 5 х 5 называется устойчивым в автомате А = (5, X, 5), если

е 5). (Уж ех) ((аь^а) е р к. ергу5х & к я? Ерг15х (¿^(зО^Двг)) е р).

Автомат А = ((5, />), X, 6). где р- устойчивое в А нетривиальное отношение порядка, будем называть упорядоченным автоматом (коротко: у-автоматом). При этом отношение р называется порядком, автомата А■ Если р - устойчивое отношение линейного порядка, то автомат А называется линейно упорядоченным автоматом (коротко: л.у. автоматом..), а отношение р — линейным порядком автомата А.

Автомат А называется: [линейно] упорядочиваемым (коротко: о-авгпоматом [О-автоматом:}), если его можно превратить в [линейно] упорядоченный автомат.

Пусть А = (5. X, 8) - произвольный автомат, |5| ^ 2. Положим по определению

((5, с), 5) € 6,

{(з1,рх),з2) € 5: (зге-5) (.((«1,Р)^) 6 5 & ((¿,х),в2) € 5)

для произвольных «1, &2 £ 5, р £ X*, х £ X, где Л** - множество всех слов в алфавите X, включая пустое слово е, а символ ": " означает эквивалентность по определению;

Sp :— {(.s'i, я 2) G S x S : {(s\,p), s*} G S) для произвольного слова

p e x*.

Подмножество S* Ç S состояний автомата A называется устойчивым в А, если 5X(S*) С S* для каждого х Е X, где

SX(S*) := {s G S : (3/ G S*) {(s', s) G

- срез отношения 8X через подмножество S*.

Автомат A* — (5*, X, 5*) называется подавтоматом автомата А, если S* - устойчивое подмножество в автомате A, a S* = 5П ((5* x X) x S*). В дальнейшем будем писать А* = {S*, X. ¿). Через Subyl обозначается решетка всех подавтоматов автомата А. Среди подавтоматов автомата А выделяются сам автомат А п пулевой подавтомат О = (0, X, 0).

Графом автомата А ~ (S, X, 5) пазывается ориентированный граф (орграф) G(A) = {S, а), где с* := : х £ -Y}. Рассмотрим на мпо-

оо

жестве S квазппорядок т := ( [J ап) U As, где Дs '■— {(s, s) : s G 5}

n=1

- диагональ в множестве S, и эквивалентность а := т П г-1. В работах М.А.Спивака [15], [16] а называется отношением непосредственной связности, а г - отношением достижимости автомата А. Классы эквивалентности а (т.е. элементы фактор-множества S/a) называются [16, с.34] с,лоями автомата А. Отношение а будем называть отношением расслоения автомата А. На множестве S/а слоев автомата А введем отношение порядка <3, положпв

Si <S2:<=> (Vsi G51)(V52GS2)((sbs2)Gr).

ОС

Отношение эквивалентности 7 := (J (г U т-1)" назовем отпошенпем

п=1

графической свжзност.и ( Г-связности) автомата А. Ненулевой втомат А пазывается [14, с.22-23]

- сильно связным, если любые два его состояния достижимы друг из друга, т.е. имеют место равенства г = S x S Sub.A = {О, Л};

- связным, если пересечение любых двух его ненулевых подавтоматов отлично от <0>.

Квадратом автомата А называется автомат А2 = (S2,X,5), где S2 := S x S, S С (S2 x X) x S2,

5r:={((ii,ii),(s2,<2))E52xS2:(.»i,.92)e5, & (h, h) G ¿Л

для всех х £ X.

Ниже везде под "автоматом" понимается автомат с числом состояний не менее двух.

Второй параграф первой главы посвящен установлению эффективного критерия упорядочиваемости автомата. С этой целью рассматривается автомат Л\ — (S\,X, ¿д), где 5д := 52 \ As, := 5 П П((5д х X) х 5д), и для него вводятся, как было указано выше, отношения непосредственной связности S, достижимости т, расслоения а, Г-связности 7.

Обозначим через Bin"'' совокупность всех антирефлексивных бинарных отношений на множестве 5, т.е. Bin'"' :— {р С S х S : рГ\ As = 0}.

На множестве В'т%г введем четыре унарные операции Т, Q, С, R следующим образом (в определениях р £ Binasr).

00

а) Т(р) •.— pir \ Аs, где ptr = (J рк - транзитнвное замыкание отно-

k=1

тения р.

б) Q(p) := Цг).

в) ОД :=С?(ЗД).

г) Положим С10) := С(р), и Сп{р) := С(Сп~1{р)) при п > 2. Легко видеть, что для любого р Е Bin"r будет

рСС(р)СС2(р)С.... (1)

Пусть для данного отношения р цепь (1) стабилизируется на шаге кр, т.е. Скр(р) = Скр + 1(р) — ..., где кр € N (стабюшзнруемость цени (1) следует из конечности множества 5). Тогда положим:

Л{р):= Ск"(р).

Заметим, что Я является оператором замыкания на упорядоченном множестве (у-множестве) (Bin%r, С).

Обозначим через Огс1Л совокупность всех отношеннй порядка, устойчивых в автомате Л. У-множество (Ог<1Л, С) является П-нолурешеткой с иаименьпшм элементом А5. Если автомат Л является ^-автоматом, то атомами полурешеткн (Ord«4, С) будут в точности все минимальные (по включению) порядки автомата Л.

Условимся далее для нетривиального порядка иС 5x5 обозначать и>* := и \ As- Порядок w С 5x5 о-автомата А = (S,X,6) назовем главным, если oj* — R(p). где р - некоторый антисимметричный слой автомата Л\.

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

ТЕОРЕМА 1.

1. Для произвольного автомата Л = (S,X,5) следующие условия эквивалентны:

а) автомат Л можно упорядочить;

б) среди сильно связных подавтоматов автомата Дд = (5'д, X. дд) найдется автомат Р = такой, что отношение R(p) является антисимметричным.

2. Пусть Л = {S,X,S) - произвольный о-автомат, ш - некоторый нетривиальный порядок на множестве S. Следующие условия эквивалентны:

а) и является минимальным порядком автомата Л:

б) ui* = R(p'), где р' - множество состояний некоторого сильно связного подавтомата автомата Лд, и для каждого сильно связного подавтомата Р = (р, X, 5а) автомата Д'д, если р С ш, то R(p) = ш*.

3. Каждый порядок о-автомата Л является объединением некоторого множества главных порядков этого автомата.

На основе теоремы 1 в работе предлагаются алгоритмы полиномиальной сложности для проверки упорядочиваемое™ автомата и для вычисления множества всех минимальных порядков автомата.

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

Следующая теорема уточняет известную теорему Джонсона п Сей-ферта (см. [14, с.27]).

ТЕОРЕМА 2. Любая конечная дистрибутивная решетка пзоморфна решетке подавтоматов о-автомата с двумя входными сигналами.

Далее в терминах решетки Sub Л характеризуются о-автоматы, принадлежащие двум важным классам, - классу (вполне определенных) групповых автоматов [6, с.49] п классу автономных автоматов.

ТЕОРЕМА 3. Групповой автомат Л можпо упорядочить тогда и только тогда, когда он не является связным.

ТЕОРЕМА 4. Автономный автомат Л можно упорядочить тогда и только тогда, когда он не является спльно связным.

Существуют спльно связные и связные, но не спльно связные автоматы с двумя входными сигналами и произвольным числом состояний, которые можно упорядочить, п которые нельзя упорядочить (теорема 5).

Автомат А назовем о-критическим, если он является о-автоматом, но любой его собственный подавтомат уже не обладает этим свойством. Далее в работе подробно изучаются «-критические автоматы.

ТЕОРЕМА 6. Ретпетка подавтоматов любого о-крнтпческого автомата имеет не более двух коатомов.

В следующих двух теоремах дается описание »-критических автоматов.

ТЕОРЕМА 7. Пусть А = 6) - произвольный автомат, ре-

шетка подавтоматов которого имеет 2 коатома, н пусть <91, С 5 -максимальные элементы у-множества (5/ст. <) слоев автомата А. Тогда следующие условия эквивалентны:

1) автомат А является о-критическим автоматом;

2) автомат А не имеет собственных о-иод автоматов и истинно следующее условие:

(3*1 е 5ь«2 6 52) (Ур <Е А'*)([«1 е рг^ & в2 ерггбр] => => [(гР(«1) е ^ & е 52) V гр(81) - гр(в2)]).

Пусть А — (Я, X, 5) - произвольный автомат, решетка подавтоматов БиЬД которого пмсет 1 коатом. Тогда этот автомат будет иметь точно один максимальный (в смысле порядка <) слой. Обозначим множество состояний этого слоя 5о, и пусть := Б\ 5У,. Определим также (частичный) автомат Ао = (5о,Х, ¿'о), где 5о :— 6 П ((5о х Л") х 50). Т.к. подмножество £0 - сильно связное, то автомат Аа будет сильно связным.

ТЕОРЕМА 8. Пусть »4 = (Я,Х, 6) - произвольный автомат, решетка подавтоматов которого имеет 1 коатолг. Тогда следующие условия эквивалентны:

1) автомат А является «-критическим автоматом;

2) автомат А не имеет собственных о-подавтоматов и истинно хотя бы одно из следующих двух утверждений (определения для 5о, ^ и Ао см, выше):

(A) (3*1 е 50,в2 £ (Ур 6 А"*)([я1 6 рг^р & € рггЭД =>

[(6р(81) ф 5р(.ь-2)) (<*„(*,) 6 <У0 & 5р(82) € 5^]);

(B) частичпый автомат Ао = (5*о, А",¿о) обладает порядком со, который удовлетворяет условию:

(Ух е X) (\/5'1, 52 е 5 : («1, э2) € и>,ф 52, «1, 52 € рг 1 дх)

Последний, четвертый, параграф первой главы целиком посвящен изучению вопросов доопределения частичных у-автоматов. Задачи доопределения частичных автоматов различных классов являются важными для приложений, п рассматривались во многих работах (см. кнхг-ги Брауэра [2, гл.4], В.А.Твердохлебова [17, §3.2], М.К.Чиркова [19, гл. 6] и др.). Аналогичные задачи - продолжения частичных операций - изучаются и в общей алгебре (см. книгу Е.С.Ляшша и Л.Е.Евсеева

[П])-

У-автомат В — ((5, и), X, 8') назовем доопределением у-автомата А = ((5, и>), X, 6), если 6 С 8'. Понятно, что доопределение частичной функции переходов 8 производится независимо по каждому входному сигналу х £ А, так что задачу доопределения достаточно рассмотреть только для автономных частичных у-автоматов.

Пусть А = ((£, и;), 8) - частичный автономный у-автомат, 0 С РП 8 С С 5. Обозначим через С(8) множество всех изотонных преобразований ■р у-множества (5, ш) таких, что 5 С. ч>. Введем в рассмотрение обыкновенный (неориентированный) граф С(5) = (V, Г), где У {(•*,£) £ 6 5 х 5 : 8 и £ С(<5)} (вершины графа), а Г (множество ре-

бер графа) состоит из всевозможных двухэлементных множеств вида И = {(з,«),(м, и)}, где (в, (и, у) € 5 X 5 , а ф и и 5 и ц £ С(5). (Предполагается, что С(8) ф %.) Заметим, что граф 0(5) является к-дольным, где к := |{я € : (3/ £ Б)(8 и (М)} €

Пусть (Р, - у-множесгво, А С Р, Аф 0. Верхним [нижнилг] конусом множества А называется множество ЛА := {а1 £ Р : (Уа £ А) (а ^ < ж)} [Ау := {х £ Р : (V« € А)(х < а)}]. Далее для а £ Р вместо {о}й [{°}У] будем писать ад [а7].

Следующая теорема решает задачу доопределения частичного авто-помного у-автомата.

ТЕОРЕМА 9. Пусть Аш = ((Б, и), 5) - частичный автономный у-автомат, (5: 5 —>5' частичная функция переходов.

I. Пусть я £ 5" и .9 ^ рг\8. Функция переходов 8 может быть доопределена на состоянии д тогда и только тогда, когда выполнено одно из следующих четырех условий:

1) *(*7) = 0 & ¿(5Д)=0;

2) ф7) ф 0 & 6{зА) = 0 (¿(в»))А ф 0;

3) 5{я*) = 0 & ф0=> (¿(в*))7 ф 0;

4) 5{з7) ф 0 & 6(ал) ф0=> П (5(.зл))7 ф 0.

Таким образом, автомат А^ допускает доопределение тогда и только тогда, когда у него найдется состояние s £ рг\8, удовлетворяющее одному из условий 1) - 4).

II. Пусть S1 С S. S' ф 0, S' П pr i Л = 0. Функция переходов <) может быть доопределена на всех состояниях из множества 5' одновременно тогда и только тогда, когда в графе G(ó) — (V, Г) существует клика К С V со свойством ргг К = S'.

Описание автономных частичных у-автоматов, которые можно доопределить до вполне определенных: у-автоматов, дает

ТЕОРЕМА 10. Пусть Аи = ((S,w),8) ~ частичный автономный у-автомат, |5 \pri<5| = к, к^ 1.

Автомат можно доопределить до вполне определенного автомата тогда и только тогда, когда выполнены следующие два условия:

1) граф G(S) - fc-дольный;

2) d графе G(S) существует fc-клпка (т.е. клика мощности к).

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

Введем на множестве P(Tii,naJ) всех подмножеств совокупности Birí£ три унарные операции Т, G н S. Пусть R С Bi7i"sr, R ф 0.

а)Т(Я):=№) : р Е R}f Т(0) := 0.

б) Операцию G склеивания па пересечениям множества fí бинарных отношений определим следующим образом.

Рассмотрим граф Г(/?) = (R,tj), где отношение г] задается равенством: г) := {(pi,p2) € R х R : р\ П p¿ ф 0}. Пусть {Г; : i £ 1} - совокупность всех компонент связности графа Г(R). Обозначим через Ri множество вершин графа F¿, i £ I. Тогда будут верпы равенства: |J№ : г е 1} — R и R( П Rj = 0¡ при; всех i,j € I, г ф ].

Положим теперь G(R) :={ U Р ■ i € -О, G(0) := 0-

p£R,

в) E(R) := G(T(Я)) для любого R С Вгп%т.

По определению, Sl{R) ;= S(i?), a Sn(R) := E,{Sn~\R)) при п £ N, п > 2.

Множество R С Bina¿r будем называть полной ортогональной симметричной (П. О. С.-) системой антирефлексивных бинарных отношений, если R удовлетворяет следующим условиям:

1) U {р : P&R} = Si, где S% ~ S2 \ As (полнота);

2) для любых /),(7ЕЙ, еслп.р ф а, то р П а = 0 (ортогональность);

3) для любого р £ Я имеем р~1 £ Я (симметричность).

Г1.0.С.-система Я С Bingr называется правильной, если каждое отношение р е R является строгим порядком на множестве S.

Правильная П.О.С.-спстема Я = {pi, р~' : i £ 1} по определению допускает согласование, если найдется такая система чисел {e¿ : i € I}, где £¿ £ {1,-1} при всех г £ I, что отношение (J{p¡' : i £ 1} есть строгий линейный порядок на множестве 5.

Пусть Я С Biiiasr есть ILO.С.-система антирсфлекспвных бипарных отношений на множестве S. Обозначим через p,n(R), п £ N, эквивалентность на множестве 5д, соответствующую разбиению Sn(R) этого множества. Очевидно, что /¿i С /л2 Q____ Так как множество S конечно, то эта цепь стабилизируется на некотором шаге р(Я), т.е. будет ßp(R) ~ l'pt — • • • > где р(Я) £ N. При этом имеет место равенство: /хр(Я) — U{/'¿ 1 ^ i ^ р(Я)}. Разбиение множества 5д, отвечающее эквивалентности р„(ц), обозначим lim Sn(R), т.е.

lim Sп(Я) := Sl/,ip{R)-

п—>оо

Из определения следует, что liin Sn(R) есть П.О.С.-система антире-

U —оо

флексивных транзитивных бинарных отношений на множестве 5.

Следующее понятие является основным во второй главе.

Определителем автомата А = (S, X, 5) называется П.О.С.-система Dcfcy4 аптирефлекспвных транзитивных бинарпых отношений на множестве 5, определяемая равенством

DeM := lim §n(5^/7).

п.—»oc

Det А является носителем той информаци о линейных порядках автомата А, которая в неявном виде содержится в описании функции переходов этого автомата.

Автомат А будем называть прав-ильным, если Det.4 есть правильная П.О.С.-спстема.

Одним из основных результатов диссертации является следующая теорема - критерий линейной упорядочивасмости автомата.

ТЕОРЕМА 11. Для произвольного автомата А ~ (S,X,S) следующие условия эквивалентны:

1) автомат А можно линейно упорядочить;

2) автомат А является правильным и его определитель DetA допускает согласование.

Точность условны теоремы 11 гарантирует утверждение 3, в котором приведен пример правильного (частичного) автомата, который нельзя линейно упорядочить.

Определитель Ое1,_А можно вычислить за полиномиальное (от числа состояний автомата Л) время. В работе показано (теорема 12), что задача проверки того, допускает ли правильная П.О.С.-система Л = = {(->1 Р7' : ^ п\ согласование, сводится к задаче поиска 14-

КЛ1ШИ в некотором специальном N-дольном графе, где N — С^, который эффективно вычисляется по системе Д.

Во втором параграфе изучаются вопросы линейной упорядочи-васмости асинхронных автоматов. Вполне определенный автомат А = (5, X, <5) называется асинхронным,, если 5(а,хх) = 5(5, х) для всех х Е X и в е 51. Такие автоматы имеют многочисленные приложения (см. кнпгу В.Б.Кудрявцева, С.В.Алешина, А.С.Подколзипа [10, с.35]). Эффективный критерий линейной упорядочиваемости асинхронного автомата дает

ТЕОРЕМА 13. Для асинхронного автомата А = (3,Х,5) следующие условия эквивалентны:

1) автомат А можно линейно упорядочить;

2) автомат А является правильным.

Проверка выполнимости этого критерия может быть произведена за полиномиальное (от числа состояний автомата) время.

Из теоремы 13 выводится одно необходимое условие линейной упоря-дочиваемости произвольного вполне определенного автомата (следствие 13.2), которое допускает проверку за полиномиальное (от числа состояний автомата) время.

В третьем, заключительном, параграфе второй главы изучаются вопросы доопределения частичных автономных 0-автоматов. Показано (лемма 18), что любой частичный автономный л.у. автомат можно доопределить до вполне определенного автономного л.у. автомата. Предлагается эффективный метод вычисления множества всех линейных порядков частичного автономного 0-автомата (теорема 14).

Автор выражает глубокую искреннюю благодарность своему научному руководителю Вячеславу Николаевичу САЛИЮ за предложенные задачи, постоянное внимание к работе и большую помощь при проведении исследований.

ЛИТЕРАТУРА

1. Агибалов Г.П. Дискретные автоматы на полурешетках. Томск: Изд-во Томского ун-та, 1993.

2. Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь, 1987.

3. Габовпч Е.Я. Линейно упорядоченные полугруппы и их приложения // УМН. 1976. Т. 31, N1 (187). С. 137-201.

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

5. Гечег Ф. О произведениях упорядоченных автоматов. II// Acta Sei. Math. 1964. V. 25, N1-2. R 124-128.

6. Глушков B.M. Абстрактная теория автоматов // УМН. 1961. Т. 16, N5 (101). С. 3-62.

7. Горбатов В.А. Теория частично упорядоченных систем. М.: Сов. радио, 1976.

8. Ильичева И.П., ПеченкинВ.В. Контроль структурных автоматов по стабильным отношениям // Методы и сист. технпч. диагностики. Саратов, 1985. Вып. 5. С. 35-43.

9. Когаловский С.Р., Солдатова В.В. О решетках конгруэнции частичных алгебр. II//Упорядоч. множества и решетки. Саратов, 1991. Вып. 10. С. 56-69.

10. Кудрявцев В.Б., Алешин С.В., Подколзип A.C. Введение в теорию автоматов. М.: Наука, 1985.

11. Ляпип Е.С., Евсеев А.Е. Частичные алгебраические действия. СПб.: Образование, 1991.

12. Розен В.В. Игры с упорядоченными исходами // Изв. АН СССР. Тех. киб. 1977, N5. С. 31-37.

13. Рубанович Г. Упорядоченные унарные алгебры // Уч, зап. Тартус. гос. ун-та. 1971. Вып. 281. С. 34-48.

14. Салий В.П. Универсальная алгебра ц автоматы. Саратов: Изд-во Саратовск. ун-та, 1988.

15. Спивак М.А. Трактовка теории автоматов методами теории отношений // Проблемы кибернетики. М.: Наука, 1964. Вып. 12. С. 69-97.

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

17. Твердохлебов В.А. Логпческпе эксперименты с автоматами. Саратов: Изд-во Саратовск. ун-та, 1988.

18. Фейнберг В.З. Унарные алгебры и их группы автоморфизмов // ДАН БССР. 1969. Т. 13, N1. С. 17-21.

19. Чирков М.К. Частичные автоматы. Ленинград: Изд-во Ленинградок. ун-та, 1983.

20. Arbib М. Tolerance automata // Kybernetika. 1967. Y. 3, N3. P. 223233.

21. FarrE.H. Lattice properties of sequential machines // J.Assoc. Comput. Math. 1963. V. 10, N3. P. 365-385.

22. Grzymala-Busse J.W. Operation-preserving functions and autonomous factors of finite automata // J. Comput. and System Sciences. 1971. V. 5. P. 465-474.

23. Lustig M. On isotone and homomorphic maps of ordered unary algebras // Acta Math. Acad. Sci. Hungaricae. 1971. V. 22, N3-4. P. 431- 439.

24. Simovici Dan A. On the theory of reduction of semilatticial automata // An. S?ti. ale Univ. "Al.I.Cuza" Din Ia§i. (Ser. Noua). Sec. la. 1976. V. 22, N1. P. 107-110 .

Основные результаты диссертации опубликованы в следующих работах:

А1. КацМ.М. О критерии линейной упорядочивасмости идемпотентного автомата // Методы п сист. технич. диагностики. Саратов, 1993. Вып. 18. С. 75-77.

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

A3. Кац М.М. О критерии упорядочиваемости автомата // Тезисы докладов на XI Международн. конф. по пробл. теор. киберн. Ульяновск, 1996. С. 89-90.

А4. Кац М.М. Эффективный критерий упорядочиваемости конечного автомата // Теоретические проблемы информатики и ее приложений. Саратов, 1997. Вып. 1. С. 58-66.

А5. Кац М.М. Критерий линейной упорядочиваемости асинхронного автомата / Саратовский гос. увит. Саратов, 1997. Деп. в ВИНИТИ 08.05.97, N 1562-В97. 21 с.

А6. Кац М.М. Критерий линейной упорядочиваемости частичного автомата // Изв. вузов. Математика. 1997. N 10.