Вопросы кибернетики. Алгебра. Гипергеометрия. Вероятность. Моделирование. М.: НИИСИ. 1999. С. 119-181.
© А.В.Коганов

Введение.

Понятие индукторного пространства  [1] [2]  первоначально было введено для получения единобразного описания математических моделей процессов различной природы в непрерывных, дискретных или смешанных пространствах. Такие модели требются в приложениях к технике, биологии, экономике и отсутствие единого языка описания процессов в разных пространствах приводило к построению аналогичных теорий и методов для каждого типа моделей. Особенно сложно описывать процесс с неперывной и дискретной составляющей, если между ними есть взаимодействие. Индукторные пространства позволили построить единый язык для описания моделей, построенных в форме локального описания процессов (типа дифференциальных уравнений, разностных схем, сетей Петри, и т. п.), и доказать общие теоремы автоматного представления процессов и устойчивости. Дальнейший анализ показал, что класс таких пространств содержит кроме топологий и графов новые объекты, которые можно интерпретировать как непрерывные графы. При этом обобщается известная теорема о изоморфности конечных групп автоморфизмам графа: каждая группа изоморфна автоморфизмам некоторого индукторного пространства с одновременным гомеоморфизмом по сходимости, если группа топологическая. Появляется возможность представлять действие произвольной группы на любом топологическом (индукторном) пространстве, как множество автоморфизмов некоторого пространства, куда исходное вложено. Такие пространства названы изображениями групп и действий  [3] . Переход на язык нечетких множеств позволяет определить нечеткое индукторное пространство и непрерывную деформацию одного пространства в другое в классе нечетких индукций. Через аппарат изображения групп можно определить непрерывную деформацию одной группы в другую. С индукторными пространствами можно связать особый класс градуированных алгебр, так, что по алгебре можно восстановить индукцию ( в общем случае нечеткую), и непрерывной деформации индукций соответствует непрерывное преобразование алгебр. Таким образом, можно определить квантовую деформацию групп через деформацию алгебр.

1. Основные определения и обозначения.

1.1. Определение 1. Понятие индукторного пространства.

1a. Отношение индукции (И-отношение) I - это отношение на прямом произведении множества T ( далее, множество точек; его элементы -"точки"), и множества его подмножеств bool(T):

I Н T ×bool( T )

Такое отношение будем обозначать [T,I], а его элемент будем записывать в форме (t,v) ~ I , где t О T , v М T . Если есть такой элемент, то v назовем индуктором точки t, а t -центром индукции подмножества v. Количество индукторов точки или центров индукции подмножества может быть любым.

Для отношения индукции можно определить квазитопологические понятия структуры подмножеств точек. Область IG подмножества G из T -это множество точек G, входящих в него вместе со своим индуктором. Петлевыми назовем точки, являющиеся своими индукторами: (t,{ t }) ~ I; LG - подмножество петлевых точек в G. Внутренность JG - непетлевые точки области: JG = IG\LG. Границей GG подмножества G из T назовем точки из G, не вошедшие в его внутренность :

GG = G \JG .

1b. Индукторным пространством (И-пространство) называется пара (T,I), где T - множество точек ("носитель"), I- отношение индукции ("индукция"), удовлетворяющее следующим аксиомам.

Аксиома включения:точка содержится в любом своем индукторе:

(t,v) ~ I Ю t О v

Аксиома объединения:объединение индуктора точки a с любым индуктором любой точки его области является индуктором a:

(a,v) ~ I, b О Iv, (b,u) ~ I Ю (a, v Иu ) ~ I

Аксиома пересечения:пересечение любых индукторов одной точки является индуктором этой точки:

(a,v) ~ I, (a,u) ~ I Ю (a, v Зu ) ~ I

Аксиома границы:для каждого индуктора объединение его внутренности и всех индукторов точек его границы совпадает с объединением всех индукторов любого его центра:

(a,v) ~ I Ю Jv ИFGv = F{ a } где для m М T  Fm = Иw | (t,w) ~ I, t О m .

Множество F{ t } не обязательно является индуктором t. Оператор F называется полным индуктором точки или подмножества.

Аксиома слитности:внутренняя точка индуктора, имеет вложенный индуктор, граница которого вложена в границу объемлющего:

(a,v) ~ I, b О Jv Ю $(b,u) ~ I  u М v, Gu М Gv .

1.2.Определение 2. Понятие индукторного изображения.

2a. Гомеоморфизм индукторных пространств (A ,I_a ) и (B,I_b) означает отображение g:A ® B, такое ,что

(t,v) ~ I_a Ы (gt,gv) ~ I_b

2b. Гомеоморфизм на себя назовем автоморфизмом. Обозначение: aut(T,I) - группа автоморфизмов и-пространства (T,I);

2c. Индукторное пространство является индукторным изображением ( И-изображением, изображением ) некоторой группы ( изображает группу ), если группа всех автоморфизмов этого пространства изоморфна данной группе.

Если группе изоморфна подгруппа автоморфизмов И-пространства, удовлетворяющих какому-то дополнительному условию, то будем говорить об условном изображении при данном условии.

1.3. Основные операции над И-отношениями и пространствами.

1.3.1. Операция построения И-пространства (T,I_s) по отношению индукции I_o на носителе T. Обозначение I_s = space(I_o). Построение индукции производится путем введения в исходное отношение индукции новых элементов, таким образом, чтобы монотонный предел отношений удовлетворял всем аксиомам И-пространства. Введем операторы преобразования отношения индукции I.

Оператор eI: если (t,u) ~ I, t П u то заменяем этот элемент на (t,uИ{ t}) ~ I . Это преобразование делается с каждым элементом индукции.

Оператор uI: если (a,v) ~ I, b О v, (b,u) ~ I, то ввести в индукцию элемент (a, v Иu ) ~ I . Проверка делается для каждой пары элементов.

Оператор iI: если (a,v) ~ I, (a,u) ~ I то ввести в индукцию элемент (a, v Зu ) ~ I . Проверка делается для для каждой пары концентрических индукторов.

Оператор bI: для каждого элемента (a,v) ~ I если не выполнена аксиома границы, то центр делается петлевой точкой - вводится элемент (a,{ a } ) ~ I. Для петлевой точки аксиома границы верна.

Оператор tI: если для некоторых (a,v) ~ I, b О Jv не выполнена аксиома слитности, то вводится в элемент (y,w) ~ I  , где   w = Иu | (b,u) ~ I, u М v .

Пояснение. По построению Gw М Gv . Иначе имеется элемент (c,z) ~ I, c О Gw, c П Gv . Но тогда для некоторого (b,q) ~ I  c О q , следовательно, по аксиоме объединения, (b, q Иz ) ~ I, z М w, c О Jw . Поскольку Gw ЗJw = Lw , c - петлевая точка из Gv, что противоречит определению c. Однако возможно Gw = Ж. Если при этом w № Fb , то нарушится аксиома границы, и требуется работа оператора b. ^[¯]

Через эти операторы операция space() определяется формулой

space( I ) = { uibt }eI

где фигурные скобки означают циклическое бесконечное повторение заключенной в них последовательности операторов . Поскольку эти операторы монотонно увеличивают отношение индукции, как множество элементов индукции, то имеется предельное отношение индукции. Оно инвариантно относительно применения каждого из u,i,b,t, что означает выполнение аксиом объединения, пересечения, границы и слитности соответственно. Аксиома включения выполняется на всех шагах итерации после начального применения e, и сохраняется в пределе: каждый из итерируемых операторов не нарушает включения. Оператор space не меняет индукторных пространств, и у него нет других инвариантных отношений индукции.

1.3.2. Прямое произведение отношений индукции [T₁,I₁] и [T₂,I₂] определяется формулой

I = I₁ ×I₂ = { ( (a,b), v ×u ) ~ I | (a,v) ~ I₁, (b,u) ~ I2 }.

Прямое произведение индукторных пространств определяется как

(T,I) = (T₁,I₁)×(T₂,I₂) = (T₁ ×T₂, spase(I₁ ×I₂ ) ) ; I = I₁ ДI₂ = spase(I₁ ×I₂ ) .

1.3.3. Объединение индукторов двух отношений [T₁,I₁],[T₂,I₂]. Это отношение индукции вида [ T₁ ИT₂, I], где I = I₁ *I₂ = {(a, v Иu) ~ I | (a,v) ~ I₁, (a,u) ~ I₂}, v = Ж for  a П T₁, u = Ж for  a П T₂ .

Объединение индукторов двух пространств ( T₁,I₁ ) *( T₂,I₂ ). Это И-пространство вида (T₁ИT₂,I), где I = I₁ \odot I₂ = spase( I₁ *I₂) .

1.3.4. Соединение индукций двух отношений [ T₁,I₁],[T₂,I₂]. Это отношение индукции вида [T₁ИT₂,I], где I = I₁ ИI₂ .

Соединение индукций двух пространств ( T₁,I₁ ) + ( T₂,I₂ ). Это И-пространство вида

(T₁ИT₂, I) , где I = I₁ + I₂ = spase( I₁ ИI₂) .

Кроме того, над отношениями индукции допустимы все теоретико-множественные операции, а к их результату можно применить space(). Вне своего множества точек индукция доопределяется, как пустое множество индукторов точки: для [T,I], a П T Ю { (a,v) ~ I } = Ж.

1.3.5. Перенос отношения индукции [T,I] на подмножество точек S М T. Перенесенное И-отношение [S,I/ S],I/ S = {(t,vЗS) ~ I/ S | t О S,(t,v) ~ I}.

Перенос индукции (S,IЇ S), IЇ S = space(I/ S). Если исходное И-отношение является индукцией, то перенесенное отношение I/ S может не быть индукцией.

2. Основные примеры индукторных пространств.

Понятие отношения индукции, как подмножество T×bool(T), дополняет понятия графа, как подмножества T×T, и топологии, как подмножества bool(T). Однако топологии и графы могут рассматриваться, как индукторные пространства.

2.1. Направленный граф (далее "колчан") можно рассматривать как индукторное пространство. Стрелу из вершины x (исходная) в вершину y (приемная) далее будем обозначать (x ® y) . Открытым подграфом назовем произвольное подмножество вершин и совокупность всех входящих в них стрел, а его замыканием - подграф, полученный добавлением к открытому всех исходных вершин его стрел. Подграф сопряжен вершине, если до нее есть путь по стрелам из любой его вершины. В качестве индукторов точки t следует брать все замыкания сопряженных ей открытых подграфов. Если есть петлевая стрела (x® x), то точка x делается петлевой: (x,{ x } ) ~ I. По такой индукции граф восстанавливается однозначно. Возможны и другие индукции, описывающие граф. Данную индукцию будем считать канонически соответствующей графу по умолчанию. Конечность графа не предполагается.

Ненаправленный граф (далее- "граф") можно рассматривать, как колчан с симметричными парами стрел (x® y),(y® x) (далее- "ребра" (x« y) ).

"Дискретное время" - колчан с вершинами { 0;1;2;....} и стрелами (0® 0),(i® i+1) для всех i. Используется в теории конечных автоматов и в информатике, как дискретное время (такты работы).

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

2.3. Направленная прямая. Множество точек - действительные числа. Индукция
I = { (x, [y;x]) ~ I | y < x }. Индукторы точки - это отрезки, в которых она является правым концом. Такое пространство не является ни колчаном ни топологией. Это не колчан, поскольку у точки нет минимального индуктора, что обязательно для колчана. В топологии объединение индукторов, содержащих точку внутри, является индуктором этой точки. Но [x-1; x]И[x-1; x+1] = [x-1; x+1] не является индуктором x на направленной прямой. Это пространство можно рассматривать, как непрерывную модификацию дискретного времени, обладающую, в отличие от обычной числовой оси, только односторонней сходимостью к любой точке. Это позволяет моделировать необратимость времени для реальных процессов.

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

2.4.1. Определение. a) Индукторное пространство непрерывно в точке, если эта точка не имеет минимального по вложению индуктора. Если минимальный индуктор есть, то точку назовем дискретной. b) Последовательность точек сходится к некоторой точке на И-пространстве ,если в любом индукторе этой точки содержатся все ее члены, начиная с некоторого номера. c) Точка И-пространства называется предельной для подмножества точек, если точки подмножества содержатся в любом индукторе этой точки. d) Индукция отделима, если для любых двух различных точек имеется индуктор одной из них, не содержащий другую. Если такой индуктор имеется у каждой точки пары, то индукция различающая. e) Пространства изоморфны по сходимости, если имеется биекция носителей, при которой последовательность сходится к точке тогда и только тогда, когда образ последовательности сходится к образу точки.

2.4.2. Замечание. Изоморфизм индукций сильнее изоморфизма по сходимости. Сходимость к дискретной точке означает, что последовательность не выходит из ее минимального индуктора, начиная с некоторого номера. Если множество пересекает минимальный индуктор точки, или содержит точку ,то эта точка для него предельная. Колчаны дискретны в каждой точке, а графы без петель неотделимы: соседние вершины содержат друг друга в минимальных индукторах.

2.5. Конические пространства являются прямым обобщением направленной прямой. Имеется бескнечно много неизоморфных типов таких пространств. Эти пространства естественно возникают при моделировании распределенных в постранстве процессов с конечной скоростью распространения взаимодействия в необратимом времени.

2.5.1. Для процессов с распространением взаимодействия вдоль фиксированных осей в n-1-мерном пространстве удобны симплекс-конические пространства Rc_sⁿ , которые определяются, как прямое произведение n направленных прямых.

2.5.2. Для процессов с распространением взаимодействия в n-1-мерном эвклидовом пространстве удобны сферо-конические пространства Rc_oⁿ. Носителем является Rⁿ. Для задания индукции вводим систему координат (x₀,ј,x_n). Содержательно, в исходном отношении индукции индуктор точки, это - часть сферического конуса, ограниченная секущей плоскостью. Конус для точки - один, а для разных точек получается параллельным сдвигом. Секущие варьируются. Формально, введем квадратичную форму конуса

C(x) = x₁²-x₂²- ј-x₁² ,

и линейную форму секущей плоскости с переменными коэффициентами

L(a,b,x) = b+a₁x₁+ј+a_nx_n, a₁ > 0, b < 0, C(a) > 0, .

Индуктор v точки y определяется, как

v_a,b,y = { x| L(x-y) і 0, L(a,b,x-y) і 0 }.

По этому отношению индукции строим пространство:

I_sc = space( { (y,v_a,b,y) | y О Rⁿ, a₁ > 0, b < 0, C(a) > 0 } .

3. Процессы на индукторных пространствах.

Индукторные пространства - удобный инструмент для описания процессов в моделях пространственно-временных явлений. Для описания распределенных аргументов в теории процессов на И-пространствах удобно ввести понятие "распределения" f(:v) , как функции f с явно указанной областью определения v.

3.1. Определение. Процессом на индукторном пространстве (T,I) называется функция распределенного аргумента p(x(:F{t}),t), где t -точка из T, x(:T) -"входное распределение" символов из "входного алфавита" X, процесс p принимает значения из "алфавита значений" Y.

Автоматом называется процесс, для которого определена "функция перехода" A:

( "t О T, (t,v) ~ I )    y(t) = p(x(:F{ t }),t) = A(x(:Jv),y(:Gv),t) .

Значения процесса-автомата в точке будем называть "состоянием" автомата в этой точке.

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

3.2. Лемма слитности. Для автомата p входное распределение x(:Jv) внутри любого индуктора любой точки (t,v) ~ I и распределение состояний на границе этого индуктора y(:Gv) определяет распределение состояний внутри всего индуктора y(:Jv).

Доказательство. A -переходная функция автомата p. Пусть b О Jv -произвольная точка внутри индуктора. По аксиоме слитности имеется (b,u) ~ I, u М v, Gu М Gv . Тогда определены x(:Ju), y(:Gu) и определяется y(b) = A(x(:Ju),y(:Gu),b). ^[¯]

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

y(:Jv) = A(x(:Jv),y(Gv), :Jv ) для (t,v) ~ I.

3.3. Лемма итеративности. Если процесс p - автомат, то на любой паре вложенных индукторов (a,v) ~ I, (b,u) ~ I, u М v, переходная функция A удовлетворяет уравнению

A(x(:Ju),A(x(:Jv),y(:Gv),:Gu),:Ju) = A(x(:Jv),y(:Gv),:Ju).

Если функция соответствующих аргументов удовлетворяет этому итеративному уравнению в пространстве, где полный индуктор точки является ее индуктором, то она является функцией перехода процесса автомата.

Лемма следует из соотношения, непосредственно вытекающего из определения функции перехода: для автомата

A(x(:Jv),y(:Gv),:Gu) = p(x(:FGu),:Gu) = y(:Gu).

По лемме слитности

A(x(:Ju),y(:Gu),:Ju) = y(:Ju) = A(x(:Jv),y(:Gv),:Ju) .

Если функция A(x(:Jv),y(:Gv),:Jv) удовлетворяет этому уравнению и для всех точек (t,F{ t}) ~ I, то определим процесс, задав произвольно y(:GT),

p(x(:F{ t}),t) = A(x(:F{ t}),y(:GF{ t}),t),

который определен в силу GF{ t} М GT . Итеративное уравнение обеспечивает определяющее свойство функции перехода.^[¯]

3.4. Структура представимости процессов.

Обозначим proc[T,I;X,Y] множество процессов на пространстве (T,I) c множествами управлений X и значений Y, а proc[T,I;X]-класс процессов с произвольным множеством значений. inpd(X,T) -множество входных распределений.

Определение. Процесс p из proc[T,I;X,Y] представляет процесс q из proc[T,I;X,Yў], если некоторая функция "перекодировки" f:Y×T® Yў для любого входного распределения x(:T) и каждой точки t О T преобразует значение p в значение q; обозначение:

p\models q Ы $f   "t    f(p(x(:F{t}),t),t) = q(x(:F{t}),t).

Отношение представимости устанавливает частичную упорядоченность на proc[T,I;X]: p і q. В каждой точке t О T процесс своим значением y порождает разбиение на входных распределениях x(:F{t}): p(x,t) = y. Распределение значений процесса порождает разбиение sbd(p) на входных распределениях x(:T): p(x,:T) = y(:T). Отношение p\models q эквивалентно sbd(p) і sbd(q) на структуре разбиений множества входных распределений.

3.5.Теорема.В классе proc[T,I;X] имеется автомат maxp, представляющий все процессы. Это единственный максимальный элемент в структуре процессов с точностью до биекции множеств значений. Следствие: каждый процесс представим автоматом.

Доказательство. Определим maxp(x(:F{t},t) = x(:F{t}) = y(t). Таким образом множество значений inp[T,I,X] = { x(:F{t}) | t О T, x О inpd(X,T) }. Свойство максимальности очевидно. Любой другой максимальный процесс должен представлять данный, и будет в каждой точке отличаться от него только биекцией множества значений, которое уникально для каждой точки. Докажем автоматность. Определим операцию объединения распределений.

И: x(:M) | M О S = x(:ИM | M О S )
где x(t) = a если ("M : t О M)   x(t) = a;    x(t) = FALSE иначе.

FALSE - выделенный символ вне всех подразумеваемых множеств значений, означает, что в данной точке результат операции не определен. Операцию И: можно применять и как бинарную. Определим функцию перехода: для (t,v) ~ I, y(b) = x(:F{b})

maxa(x(:Jv), y(:Gv),t) = x(:F{t}) = x(:Jv)И: (И: x(:F{ b }) | b О Gv ).

Для t О GT доопределим функцию перехода maxa(x(t),.,t) = x(t). Определение корректно, в силу аксиомы границы. На каждом входном распределении x(:T) значение FALSE не появляется, поскольку все F{ b } и Jv входят в T и распределения на них согласованы.^[¯].

3.6. В случае конечного числа состояний автомата строгое уменьшение по структуре процессов означает уменьшение числа состояний. Поэтому порядок в структуре процессов можно считать упорядочением по сложности автоматов и при бесконечном числе состояний. Естественно искать для данного процесса простейшую автоматную модель. Однако, такой автомат существует не всегда.

Определение.Рецептором rec(p) процесса p назовем минимальный автомат, представляющий данный процесс.

Выясним условия существования рецептора процесса.

3.6.1. Понятие сильной зависимости.

Обозначение. Для функции не менее двух переменных f(x,y) с носителем (x,y) О X×Y значения x и xў эквивалентны, если для любого y О Y  f(x,y) = f(xў,y). Соответствующее разбиение на X обозначим equ[X;f,Y], а equ[X;f,Y](x) -элемент разбиения, содержащий значение x О X.

Если E - разбиение на множестве X, W М X×Z, то обозначим E^W разбиение на W с элементами вида

{ (x,z) | x О e, (x,z) О W } где e О E .

Определение. Функция распределенного аргумента f(x(:Q),y), где x(:v) О W(v) для v М Q, y О Y -остальные аргументы, сильно зависит от покрытия M на Q, если на структуре разбиений множества W(Q)

equ[W(Q);f,Y] Ј Хequ[W(v);f, W(Q\v)×Y]^W(Q) | v О M .

Иначе - слабая зависимость от покрытия.

Пояснение Сильная зависимость означает, что если для некоторых распределений a(:Q), b(:Q)   f(a,y) № f(b,y) , как функция y, то для некоторого d О M   f( a(:d) И: z(:Q \d), y) № f( b(:d) И: z(:Q \d), y), как функция y,z.

Пример слабой зависимости. Рассмотрим функцию от бинарной последовательности x = (x₁,x2,...) где x_i О {0;1} :

f(x) = 1 если е_{i = 1}^Ґ x_i = Ґ;     0 иначе.

В качестве покрытия W = {1,2,ј} берем поточечное разбиение. Значения x(:N) на любом конечном множестве N не влияют на значение f, но имеется зависимость от всей последовательности.

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

3.6.2. Введем обозначение: y(:T) = p(x(:T),:T), которое обобщает обозначение процесса на распределенное значение его выхода. Соответственно, y(:v) = p(x(:Fv),:v).

Определение. Процесс p(x(:F{t}),t) = y(t) назовем сильно-определенным, если для каждого (t,v) ~ I функция распределенного аргумента x(:Ft) = x(:Jv)Иx(:FGv) с распределенным значением y(:Jv) сильно зависит от покрытия { F{ e}| e О Gv } на FGv. Иначе - слабая определенность процесса.

Из пояснения п.3.6.1 видно, что если на пространстве граница каждого индуктора конечна, то все процессы сильно определены, поскольку в каждой точке t значение y(t) определяется по конечному набору элементов разбиения F{e},e О Gv для поизвольного (t,v) ~ I. Например, это верно в дискретном времени (п.2.1).

Пример функции f из п.3.6.1 можно превратить в пример слабо-определенного процесса на колчане с вершинами {0,1,2,ј} и стрелами {(i ® 0)|i = 1,2,ј}. Множества входов и значений процесса совпадают X = Y = {0;1}. Определим p(x(i),i) = 1 для i і 1;

3.6.3.Теорема.Все и только сильно-определенные процессы имеют рецептор. Доказательство. Допустим процесс p на (T,I) с множествами входов X и значений Y cлабо определеный, а g -автомат, его представляющий, с функцией перехода A, множеством состояний S и функцией перекодировки f: для каждого (t,v) ~ I, x(:T), s(t) = g(x(:F{t},t) для t О T по определению

p(x(:F{t}),t) = f(A(x(:Jv), s(:Gv),t),t) = f(s(t),t).

Если процесс слабо определен, то слабо определена и функция с распределенным значением y(:T) и распределенным аргументом x(:T\FGv) И: x(:FGv) на покрытии {F{ e} | e О Gv } множества FGv для некоторого элемента индукции (t,v) ~ I. Тогда существует монотонно растущая башня D подмножеств T,   N = Иd | d О D,   d ­ N , на которой для некоторых двух входных распределений a(:T), b(:T) и каждых d О D, e О d

p(a(:T),:T) № p(b(:T),:T) = p(a(:Fd)И: b(:T\Fd),:T) = p( a(:F{ e}) Иb(:T\F{ e}), :T).

Из первого неравенства следует, что g(a(:T),:T) № g(b(:T),:T). Пусть g(b(:T),:T) = s(:T) , g(a(:T),:T) = z(:T). Тогда определим процесс G[d](x(:F{ t}),t) для всех x = x(:T), t О T.

Если t О d  &  x = a(:F{ t}), то G[d](x,t) = s(t). (1)

Заметим, что в этих точках g = z(t). Если t П d , но имеет индуктор v с непустым пересечением w = Gv Зd,то обозначим u = { e | e О w, g(x,e) = z(e) }, Q = Gv \u и определим

G[d](x,t) = A(x(:Jv), g(x,:Q)И: s(:u), t). (2)

В остальных случаях G[d](x,t) = g(x,t). (3)

Заметим, что g(x,t) = A(x(:Jv),g(x,:Q)И: z(:u),t), т. е. состояние G[d] из (2) соответствует состоянию g при склейке состояний на d, описанной в (1). Поскольку A - функция перехода автомата, то по лемме итеративности (п.3.3.) выражение (2) не зависит от выбора индуктора v при условии склейки состояний, определенной в (1). Таким образом, во всех точках G[d] получается склейкой состояний g, следовательно g\models G[d], g № G[d]. Имеется функция q перекодировки G[d](x,t) = q(g(x,t),t). В силу выбора множества d процесс G[d] представляет p с той же функцией перекодировки f, что и g: y(:T) = f(G[d](x(:T),:T),t). Покажем, что G[d] удовлетворяет автоматности. Для тех точек t П d, где w = Ж, действует (3) и для G[d] есть функция перехода, совпадающая с A. Для остальных точек G[d] соответствует функции перехода

B(x(:Jv), G[d](x,:Gv),t) = q(A(x(:Jv),g(x,:Gv),t), t) = B(x(:Jv), q(g(x,:Gv),t), t)

Последнее равенство выражает итеративность и следует из произвольности индуктора v в определении склейки (2).

В то же время любая склейка состояний на всем множестве N по выбору башни D из условия слабой определенности нарушает представление процесса p. При построении автомата G[d] по произвольному элементу башни d всегда можно выбрать больший элемент dў Й d, порождающий строго большее множество точек склеек при тех же входных распределениях a(:T),b(:T), что означает G[d]\models G[dў]. Но любая общая миноранта всех автоматов { G[d] | d О D } не может представлять процесс p, поскольку вызовет склейку состояний на всем N. Следовательно, множество автоматов { G | G\models p } не имеет минимума и рецептор rec(p) не существует.

Обратно, пусть процесс p сильно определен. В качестве множества возможных состояний искомого рецептора выберем множество Z = bool{ x(:F{ t}) | t О T, x(:T) О W(T)}. Определим оператор E на процессах, переводящий процесс в новый прцесс с множеством значений из S. Используем оператор equ построения разбиений (п.3.6.1). Обозначим

r(t) = { t} И{e| e О T, $(e,v) ~ I t О Gv }.

E(p)(x(:F{ t}),t) = equ[W(F{ t}); p(x(:F{ t}И: x(:T\F{ t}),:r(t)), x(:T\F{ t})] = s(t). (4)

Из сильной определенности p и по аксиоме границы для каждого (t,v) ~ I значение s(Gv), x(:Jv) однозначно определяет y(:Jv). Поскольку t О r(t), E(p)\models p. Обратно, если E(p)\models p, то p сильно определен. Покажем, что оператор E сохраняет сильную определенность. Если p сильно определен, то p = f(E(p)) для некоторой функции перекодировки f. Тогда E(p) = E(f(E(p))). Поскольку f является поточечной перекодировкой значения, то последнее равенство означает E(E(p))\models E(p) и E(p) сильно определен. Непосредственно из определения следует, что процесс является автоматом тогда и только тогда, когда он E-инвариантен:

g автомат Ы E(g) = g.

Если (t,v) ~ I, e О Gv, то t О r(e) и по аксиоме объединения

r(t) Н r(e) (5)

F{ e} Н F{ t} (6)

Поскольку E(p) - процесс и сильно определен, то из (6) следует наличие зависимости s(t) = func(x(:Jv), s(:FGv ), t). Из (5) и (4) и из того, что каждое распределение s(:F{ e}), e О Gv, является разбиением на множестве распределений x(:F{ e})

s(t) = func(x(:Jv), s(:Gv ), t). (7)

Действительно, если два входных распределения на F{ e}) не эквивалентны относительно значения s(t), то они по (4) соответствуют разным значениям s(e). Но соотношение (7) определяет функцию перехода для E(p), следовательно это - автомат. Допустим имеется автомат g\models p. Тогда множество распределений G(t,s) = {x = x(:F{ t}) | g(x,t) = s} должно содержаться в одном классе E(p)(x,t). Это значит, что g\models E(p). Следовательно, построен P = rec(p). ^[¯]

Из теоремы следует, что на пространствах с конечным числом точек в границе каждого индуктора каждый процесс имеет рецептор. К числу таких пространств относятся колчаны с конечным ветвлением по входящим стрелам (в том числе дискретное время), направленная прямая, обычная топология на прямой, конечнократные склейки отрезков направленных и обычных прямых, и т. п.

3.6.4. Композиция процессов. Определение. Композицией процессов p и q с общим входным алфавитом называется вектор-процесс (p,q)(x(:F{ t},t) = (p(x(:F{ t},t), q(x(:F{ t},t)).

Теорема. Для композиции процессов z = (p,q) верны следующие утверждения.

i. sbd(z) = sbd(p)*sbd(q) в смысле произведения на структуре разбиений (п.3.4.).

ii. Если p и q - автоматы, то и z -автомат.

iii. Если a и b - прцессы, и a\models p, b\models q то (a,b)\models (p,q).

iiii. rec((p,q)) = (rec(p),rec(q)) .

Свойства i,ii,iii следуют прямо из определений, а iiii вытекает из ii,iii. Использование свойства iiii значительно облегчает построение минимальных автоматных моделей сложных процессов и событий, которые часто удается представить, как композицию более простых. Использование свойства i позволяет в композиции автоматов уменьшить число (или множество) состояний по сравнению с прямым произведением.

3.6.5. Сложность описания процесса.

Разложение процесса в композицию в практическом плане упрощает описание процесса, сводя его к описанию отдельных компонент и их взаимодействия. Это не гарантированное упрощение, но, фактически, к разложению прибегают только тогда, когда это снижает сложность описания на используемом в моделировании языке. Аналогично, представление процесса в виде автомата целесообразно тогда, когда функция перехода описывается проще общей функции процесса. Это не обязятельное свойство, однако это так для большинства моделей в физике и технике. Общей теории эффективности локальных описаний в настоящее время нет, но можно привести несколько примеров того и другого типа. Для непрерывных пространств наибольший эффект получается в случае, когда модель удается записать в форме дифференциального уравнения. Правда при этом за простоту описания модели часто приходится расплачиваться высокой сложностью вычисления решения. Известны случаи, когда для ускорения расчетов разработчики отказывались от компактной дифференциальной модели, прибегая к параметрической апроксимации общего решения. Промежуточный способ описания дает метод конечных элементов, когда непрерывное пространство разбивается на малые участки, на каждом из которых процесс описывается параметрической функцией, а взаимодействие между участками описывается функциями перехода. Фактически, при этом непрерывное пространство подменяется графом соседства конечных элементов и строится автомат на этом графе с непрерывным множеством состояний. В более слабой форме это происходит в разностных схемах, где пространство заменяется на последовательность графов, соответствующих измельчению разбиения исходного пространства. Анализ этих ситуаций и других способов описания непрерывных автоматов выходит за рамки этой работы. Отметим только отсутствие универсального подхода к оценке сложности непрерывных моделей. Фактически, сложность оценивается только для каких-то специальных разложений функции, типа рядов или дробно-рациональных функций, что оставляет открытым вопрос о необходимости именно таких описаний. Ниже будут даны некоторые оценки сложности для процессов в дискретных пространствах с конечным множеством значений. Автоматы на пространствах -колчанах с конечным множеством состояний в каждой вершине являются сетями Петри. В каждой вершине такой автомат задается дискретной функцией перехода, для оценки сложности которой используется метод наиболее экономного разложения ее в итеративную схему на заданном базисе функций. Относительно того же базиса можно оценить сложность глобального описания процесса. Этот прием позволяет оценивать эффективность автоматного представления с точки зрения снижения сложности описсания процесса, хотя конкретная оценка сложности зависит от базиса. Заметим, что исходное глобальное описание процесса может не быть сетью Петри.

Обозначим Q[m,n] множество функций от n аргументов, принимающих каждый зачения 1,ј,n , со значениями в том же множестве. Эти функции будем называть бызовыми. Для функции f(x₁,ј,x_k ) с той же областью своих и аргументных значений назовем сложностью comp[m,n]f наименьшее число базовых функций которыми можно реализовать эту функцию в виде итерационной сети.

Если на пространстве (T,I) типа колчана задан процесс p(x(:F{ t}),t), то в каждой точке t он реализует функцию p_t(x(:F{t })). Для автоматного предствавления процесса в каждой точке определяется функция A_t(x(:w(t)),s(:v(t))), где r = v(t)Иw(t) -точки, имеющие стрелу на точку t и она сама, причем точки из w(t) получают все входные стрелы из r, а точки v(t) часть стрел получают из-вне; состояния s записаны в m-ичном коде s = (s₁,ј,s_k). Автоматное представление локально эффективно, если

eff(t) = comp[m,n]p_t / comp[m,n]A_t > 1 .

Для рассмотрения глобальной эффективности требуется кодировка точек пространства в m-ичном коде, чтобы было возможно разложение процесса и функции перехода по базовым функциям. Чтобы не усложнять второстепенными деталями изложение, ограничимся анализом локальной эффективности при фиксированных m,n, которые далее не указываются, как параметры. Без пояснений колчаны на множестве точек отождествляем с индукциями. Будет показано, что почти у всех процессов на колчанах автоматные представления неэффективны. Но почти у всех процессов, первоначально записаных, как сеть Петри, такие представления эффективны, т.е. любое их глобальное описание сложнее функции перехода. Это позволяет рассматривать дискретные сетевые процессы, как аналог дифференцируемых функций в непрерывном анализе.

В основе оценок лежит энтропийный метод  [4] . Рассмотрим на счетном множестве точек T семейство колчанов С с ветвлением по входящим стрелам не более n и с неограниченным ростом полного индуктора хотябы одной точки. Одна базовая функция может обеспечить одно из mⁿ разбиений множества входных слов, а итеративная схема из k базовых функций - одно из m^nk. Общее количество разбиений на не более чем m классов входных распределений на множестве из q точек равно m^q. Таким образом, доля процессов, имеющих локальное представление в точке t через k базовых функций при \sharp F{ t} = q составляет m^nk-q и стремится к 0 при q ® Ґ. Поскольку количество внутренних точек минимального индуктора точки не более n, основная сложность приходится на представление через базовые функции отображения s(x,e) входного распределения x в состояния точек e границы минимального индуктора.

Рассмотрим теперь процессы, исходно заданные на колчанах, как автоматы с конечным числом состояний ( сети Петри ). Если автоматное представление не эффективно, то функция p имеет не более сложное базовое разложение, чем функция A, включая вычисление состояния границы. Оценим долю таких сетей Петри. Допустим сложность узлового элемента в точке T в сети Петри не превосходит b базовых функций. Тогда, с помощью функций такой сложности, возможно разбить входные распределения на m классов не более чем m^nb способами. Каждый класс при этом соответствует одному из состояний узлового элемента сети. Оценим снизу количество возможных разбиений множества входных распределений на полном индукторе одной точки в сетях с базовыми узловыми функциями. Зададим в каждом узле свою независимую нумерацию (числовую перекодировку) входных символов. Всего имеется m! различных последовательных нумераций в одном узле. Используем в каждом узле e функцию max{ h(e,x(i)) | i О v(e) }, где h(e,x) - номер входного значения x при нумерации для узла, v(e)-наименьший индуктор узла. Легко видеть, что в такой сети отличие нумераций хотябы в одной точке F{ e} означает различные разбиения входных распределений по значениям процесса в точке e. Таким образом количество локально-различных процессов типа сетей Петри с базовыми узловыми функциями не меньше (m!)^q. Тогда доля процессов с неэффективным автоматным представлением не выше m^nb / (m!)^q ® 0,    q® Ґ. Следовательно, автоматное представление эффективно почти на всех сетях Петри.

4. Локальные уравнения процессов.

Математические модели типа автоматов на графах или областях многомерных пространств широко используются в приложениях математики. При этом термин "автомат" используется только в теории конечных автоматов, первоначально возникшей для исследования процессов обработки последовательно поступающей информации. Независимо развивались теории дифференциальных уравнений и разностных схем в линейных пространствах различных размерностей, метод конечных элементов, теория информационных сетей и коллективов автоматов, рекурсивные методы статистических оценок и идентификации моделей. Все эти математические объекты описываются автоматами на подходящих индукторных пространствах.Для них характерно описание распределенных параметров объекта через локальное описание связей на носителях значений этих параметров в подходящем понимании близости. Такие описания автоматов будем называть локальными уравнениями.

4.1. Понятие локального уравнения.

Пусть на индукторном пространстве (T,I) имеется автомат p с функцией перехода A: s(t) = p(x(:F{ t},t) .Зададим на T индукторное покрытие

V = { V(t) | t О T },   t О JV(t) ,

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

y(:JV(t)) = A(x(:JV(t)),y(:GV(t)),:JV(t)),

решением которого являются такие распределения y(:T), которые удовлетворяют ему при данном покрытии для всех точек t. Очевидно, что при каждом покрытии ему удовлетворяет распределение состояний автомата s(:T). Однако, иногда, уравнение на покрытии имеет и другие решения. Введем частичный порядок на индукторных покрытиях: V\prec W (V мельче W), если для всех точек t О T  V(t) М W(t). Решение на покрытии является решением на всех более мелких покрытиях. Это следует из леммы итеративности (п.3.3).

4.1.1.Определение. Распределение со значениями состояний автомата y(:T) является специальным решением локального уравненя автомата

y(:Jloc(t)) = A(x(:Jloc(t)),y(:Gloc(t)),:Jloc(t)),

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

4.1.2. Функция перехода A(x(Jv),y(Gv),:Jv) автомата p точно определена, если ее областью определения являются только такие распределения состояний, которые могут быть получены на границе индуктора при некотором входном распределении xў(:T\Jv) :

4.2. Теорема. Если функция процесса-автомата p(x(:F{ t}),t) для всех t О T сильно зависит от покрытия M = {v| (t,v) ~ I} на F{ t} , то единственным универсальным решением локального уравнения с точно определенной функцией перехода является распределение состояний автомата s(:T) = p(x(:T),:T). При слабой зависимости для некоторой точки t универсальное решение не единственно.

Доказательство. Допустим имеется сильная зависимость для всех точек. Тогда в любой точке t значение s(t) можно получить, как пересечение множеств

{ s(t)} = { p(x(:F{ t}),t) } = (И{ p(x(:v)И :xў(:Q),t) | xў(:Q) О W(Q) }| v: (t,v) ~ I ), где Q = Q(v) = F{ t}\v .

При этом

p(x(:v)И:x(:Q),t) = A(x(:Jv), g(:Gv),t);  g(e) = p(x(:v)И: xў(:Q), e), e О Gv .

Это выражение допустимо по аксиоме границы: F{ e} М vИQ = F{ t}. Если есть два универсальных решения y(:T), z(:T), y(t) № z(t) в некоторой точке t, то имеется два распределения xў(:Q), xўў(:Q) при которых для каждого индуктора этой точки v

y(t) = p(x(:v)И: xў(:Q), t); z(t) = p(x(:v)И: xўў(:Q), t);

Но тогда

s[d](:T) = p(x(:dИG)И: b(:Q), :T); G = T\F{ t};  Q = Q(d) = F{ t}\d;   s[d](t) = z = p(x(:d)И:b(Q),t);   z № s(t).

Имеется предельное распределение состояний

y(:T) = lim s[d](:T)| d­ F{ t};

это следует из того, что для любого e О JF{ t} найдется d(e) О D и (e,v) ~ I, где v М d(e). Тогда при всех d Й d(e)  s[d](e) = s[d(e)](e) = y(e). Но для всех d  s[d](t) = z. Значит y(:T) № s(:T) и является универсальным решением, что означает неединственность таких решений. ^[¯]

4.2.1. Замечание. Условие общей устойчтвости из теоремы, показывает, что это свойство не локальное и связано с полным индуктором каждой точки. Если есть локальная устойчивость, то есть и общая. Общая неустойчивость влечет локальную. На пространствах, где полный индуктор каждой точки является ее индуктором : "t О T  (t,F{ t}) ~ I, всегда есть общая устойчивость. Формально, это следует из теоремы, т.к. s(t) = p(x(:F{ t}),t), но можно заметить, что для любого процесса значения однозначно определяются по входным распределениям на элементах покрытия {F{ t} | t О T}. Это устанавливает факт общей устойчивости для всех автоматов в дискретном времени, на конечных отрезках непрерывной прямой, в ограниченных областях эвклидовых пространств, на ограниченных со стороны индукции лучах направленной прямой, на ограниченном со стороны индукции полупространстве конического пространства.

4.2.2. Приведем пример общей неустойчивости автомата на колчане

0¬ 1¬ 2¬ ј.

Определим процесс- автомат. Y = X = { 0;1 }; y(i) = p(x(:{ i;i+1;ј}),i) = max{ x(i);x(i+1);ј}; с функцией перехода

y(i) = A(x(:{ i;ј; i+n }, y(:{ i+n }) = max{ x(i);ј;x(i+n);y(i+n)} .

При каждом входном распределении есть решение на любом индукторном покрытии y(i) = 1; i = 0,1,ј; Но на входных распределениях с конечным числом единиц автоматное решение иное: s(i) = 0 при x(j) = 0 для всех j > i; s(i) = 1 иначе.

4.3. Локальная устойчивость.

В отличие от общей устойчивости, локальная устойчивость всех автоматов имеет место для очень узкого класса И-пространств. На пространстве с непрерывной различающей индукцией всегда можно построить локально неустойчивый автомат. Также, как и вслучае с общей устойчивостью, локальная неустойчивость имеет описание через внутренние свойства процесса. В дальнейшем, класс входных распределений процесса с множеством входов X на множестве точек Q будем обозначать INPD(X:Q), класс выходных распределений значений или состояний из Y обозначим OUTD(Y:Q) (один или оба аргумента могут бть опущены, если они ясны из контекста) ;

4.3.1. Определение. Процесс p на И-пространстве (T,I) имеет ветвление на индукторном покрытии M при входном распределении x О INPD(X:T), если есть два распределения значений y, z О OUTD(Y:T) таких, что z = p(x,:T), y(:T) № z(:T), и для каждого v О M имеется входное распределение b О INPD(X:T\Jv) , при котором y(:Jv) = p(x(:Jv)И: b, :Jv).

4.3.2. Теорема. . Автомат с точно определенной функцией перехода локально неустойчив т. и т. т. когда на некотором покрытии имеет ветвление.

Доказательство. Если имеется ветвление автомата p на покрытии M при входном распределении x(:T), то основное решение s(:T) = z, а в качестве альтернативного решения можно взять распределение y(:T), входящее в определение ветвления. По условию точного определения функция перехода определена на всех элементах покрытия и распределение y на всех элементах удовлетворяет функции перехода. Обратно, если имеется два решения локального уравнения на некотором покрытии M при входе x(:T), то одно из них z(:T) является распределением состояний автомата (всегда решение), а другое удовлетворяет точно определенной функции перехода и, следовательно, приняв распределения xў(:T\Jv) за b, получаем ветвление процесса. ^[¯]

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

Пример наведенной неустойчивости. Рассмотрим автомат на колчане "дискретное время" (п. 2.1.) , X = Y = { 0;1},

p(x(:{ 0;ј;i }), i ) = max{ x(0);ј;x(i)};

A(x(:{ i-k+1;јi }, y(:{ i-k}), i) = max{ y(i-k);x(i-k+1);ј;x(i)};

A(x(:{ 0}), y(:{ 0}),0) = max{ x(0); y(0) };

Последнее уравнение не точно определено, поскольку p(x(0),0) = x(0) и вариант x(0) = 0, y(0) = 1 в процессе не возможен. Из-за этого возникает наведенное локальное решение y(:T) = const = 1 при входе x(:T) = const = 0 на индукторном покрытии v(i) = { i-1;i}, i > 0 ; v(0) = { 0} . При точном определении A(x(:{ 0}), y(:{ 0}),0) = x(0) остается только автоматное решение s(:T) = const = 0. При точном определении этот автомат устойчив, как и все автоматы в дискретном времени. Далее будет исследоваться только устойчивость и неустойчивость при точных определениях функции перехода.

4.4. Анализ локальной неустойчивости.

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

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

diff(x(:F{ t}),t) = y(t) = max{ x(e)| e О F{ t} };   x О INPD({ 0;1} : T); y О OUTD ({ 0;1} : T);

Его функция перехода имеет точное определение

DIF(x(:Jv), y(:Gv), t) = max({ x(e)| e О Jv }И { y(e)| e О Gv \Jv }); (t,v) ~ I;   x О INPD;   y О OUTD;

4.4.2. Рассмотрим диффузный автомат на направленной прямой (п. 2.3.). В качестве покрытия возьмем v(t) = [t/ 2 ;t] для t > 0;   v(t) = [t-1;t] для t Ј 0; Локальная неустойчивость проявляется в неавтоматном решении при x(:T) = const = 0, y(t) = 0 для t Ј 0; = 1 для t > 0; Здесь существенно используется непрерывность пространства при построении покрытия. А пример с покрытием v(t) = [t-1;t] для t О T; входом x(:T) = const = 0 О INPD , и неавтоматным решением y(:T) = const = 1 О OUTD подходит и для дискретного колчана на целых числах со стрелами (i® i+1) .

4.4.3. Неустойчивость на конечном графе. Рассмотрим граф T с вершинами 1,2,3,4 и ребрами

4.4.4. Неустойчивость на дискретном цикле. Колчан T с вершинами 1,2,3 и стрелами (1® 2)(2® 3)(3® 2). диффузный автомат, вход x = 0 О INPD(:T), автоматное решение y = 0 О OUTD(:T), неавтолматное решение y(1) = 0; y(2) = y(3) = 1 .

4.4.5. Определение. Индукторное пространство потенциально устойчиво, если на нем локально устойчивы все автоматы; иначе - потенциальная неустойчивость.

4.4.6. Лемма. Потенциальная неустойчивость И-пространства (T,I) эквивалентна условию: имеется подмножество точек вне границы пространства M М T,  MЗGT = Ж, и индукторное покрытие V на M, для которых граница элемента покрытия любой точки подмножества t О M имеет непустое пересечение с подмножеством M: GV(t)ЗM № Ж.

Доказательство. Допустим это условие выполнено. Рассмотрим индукторное покрытие V с произвольным расширением на все T. Рассмотрим диффузный автомат. Определим понятие сцепки элементов покрытия. Элемент v сцеплен с множеством элементов g, v ~ g , если он входит в множество или если его непетлевая внутренность пересекается с границей хотябы одного из элементов множества. u(0,t) = { V(t)}, u(k+1,t) = { V(e)| V(e) ~ u(k,t) } u(t) = Иu(k,t) | k = 1,2,ј; Для t О T, положим f(t) = ИGv | v О u(t); это объединение границ всех элементов из u(t). На покрытии V при входе x(:T) = 0 О INPD кроме автоматного решения s(:T) = 0 О OUTD еще есть решение локального уравнения y(t) = 0 если f(t)ЗM = Ж;  = 1 иначе. Действительно, диффузный автомат передает состояние "1" с любой точки границы на все внутренние точки, независимо от входного распределения внутри индуктора. Если задать состояние "1" на всех точках M, то по построению это состояние распространится на все точки, для которых f(t) пересекает M. На остальных точках под влиянием нулевого входа будет состояние "0". Таким образом, пространство потенциально неустойчиво. Обратно, если на пространстве имеется локально неустойчивый автомат, имеющий два решения s(:T) № y(:T) на покрытии V при входном распределении X(:T), то рассмотрим множество M = { e | e О T, s(e) № y(t) } . Если для t О M  GV(t)ЗM = Ж то значение распределения состояний на границе элемента пкрытия совпадают в обоих решениях: s(:GV(t) ) = y(:GV(t)) = z, но тогда совпадают и значения

4.4.7. Теорема. Индукторное пространство потенциально устойчиво тогда и только тогда, когда выполнено одно из следующих эквивалентных условий:

i. на нем устойчив диффузный автомат;

ii. на пространстве любая цепь элементов индукции ("И-цепь") со звеньями вида (t,v) ~ I, (e,u) ~ I, e О Gv. вполне упорядочена в упорядочении (t,v) ~ I > (e,u) ~ I .

Доказательство. Из первой части доказательства леммы (п. 4.4.6.) видно, что при выполнении условий локальной неустойчивости явно строятся два решения для локального уравнения диффузного автомата. Если же диффузный автомат неустойчив, то это само по себе означает потенциальную неустойчивость пространства. Это доказывает i. Если имеется не вполне упорядоченная И-цепь, то либо она зацикливатся по типу (t,v) ~ I > (e,u) ~ I, t О Gu , либо неограничено убывает. В обоих случаях она является множеством M из леммы. Если все И-цепи вполне упорядочены, то предположив какое-то множество M можно в нем двигаться по убыванию одной из цепей неограничено, но наличие в этой И-цепи наименьшего элемента показывает невыполнимость этого требования. Это доказывает ii.^[¯]

Замечание. Для конечных колчанов условие ii теоремы означает отсутствие циклов. В частности, все графы потенциально неустойчивы. Для произвольных колчанов требование ii означает отсутствие циклов и бесконечных цепей против стрелок. На бесконечных пространствах имеются неколчанные примеры потенциально устойчивых пространств. Рассмотрим множество точек {0;1;2;ј} На 1,2,... строим колчан (n® n+1), n = 1,2,ј. Для точки 0 дополнительно определим индукторы вида {0; k;k+1;ј}, k = 1,2,ј. Такая индукция не соответствует колчану, но удовлетворяет условию ii.

4.5. Локально устойчивое представление автоматов.

В пункте 3.5. построен автомат maxp, представляющий любой процесс из pros[T,I;X]. Если научиться строить локально устойчивые уравнения для такого автомата, можно считать принципиально решенной задачу устойчивого локального описания всех автоматов. При этом, конечно, такое описание менее лаконично, по сравнению с локальным уравнением самого автомата, но оно универсально. Для построения таких уравнений заметим, что локальные уравнения можно строить на покрытиях, элементы которых не обязательно индукторы. Подходят любые объединения индукторов, удовлетворяющие аксиоме границы. Такие множества будем называть областями И-пространства, а соответствующие покрытия и цепи квазииндукторными ( КИ-покрытия, КИ-цепи ). Индукторные цепи и покрытия - частный случай квазииндукторных.

4.5.1.Определение. Обозначим V[m](t) множество всех точек, покрываемых КИ-цепями длины не более m с началом в (t,V(t)) ~ I. КИ-покрытие V И-пространства (T,I) назовем контролируемым, если имеется такое n, что для каждой точки t О T F{ t} М V[n(t)](t).

Контролируемые КИ-покрытия всегда существуют: можно покрыть все пространство одним элементом T. Замена любого элемента контролируемого покрытия на конечное число покрывающих его элементов сохраняет контролируемость. Поэтому описание автоматов уравнениями на контролируемых покрытиях можно считать локальным.

4.5.2.Теорема.На контролируемых покрытиях автомат maxp с функцией перехода maxa локально устойчив относительно уравнения

Доказательство. На границе пространства значения состояний точек совпадают со входом в любом решении Поскольку состояниями в точке t являются распределения x(:F{ t}), то на любом покрытии гарантируются верные состояния точек на GT, на элементах примыкающих к границе или крайних в КИ-цепях, и далее по индукции на любом конечном удалении n(t) от границы или крайних элементов КИ-цепей. В контролируемых покрытиях любая точка находится на конечном удалении и поэтому любое не автоматное решение возможно только ценой введения состояния FALSE, и решение не удовлетворяет второму неравенству. ^[¯]

5. Частично определенные процессы.

Построение автомата по процессу, проведенное в п.3, было основано на полном знании функции, определяющей процесс, как зависимость выходного распределения от входного. При этом, для достаточно широкого класса процессов (на некоторых пространствах для всех) было установлено наличие единственного минимального представляющего автомата. Но в прикладных исследованиях нередко возникает ситуация, когда процесс представлен не полным описанием, а частичным, когда выходное распределение значений процесса известно только для некоторого подмножества входных распределений. В частности, оно может быть известно только для конечного числа входных распределений на некоторых индукторах. Этот случай можно считать вариантом математической статистики, где по конечной выборке восстанавливается математическая модель процесса. Его можно назвать, также, пассивной расшифровкой автомата, когда нет возможности пробовать новые упраляющие воздействия на процесс, и модель формируется по имеющейся информации. Для такого частичного определения процесса характерно наличие бесконечного числа автоматов, минимальных в структуре автоматов, представляющих своим состоянием распределение значений процесса на известных входных распределениях. Если множество таких распределений конечно, то дополнительное формальное требование конечности и минимальности числа элементов разбиения на множестве входных распределений позволяет выделить конечное подмножество "простейших" моделей. Разумеется, при этом нет гарантии, что правильная модель - простейшая, и получение новых данных о процессе может изменить набор простейших моделей. Тем не менее прстейшие модели полезны для выявления тех свойств автомата, моделирующего процесс, которые логически следуют из известных данных о процессе. Существенно здесь и то, что если некоторая простейшая модель конечного частичного определения процесса представляет и новые данные, то она войдет в набор простейших моделей расширенного частичного определения, и тогда все новые простейшие модели образуют подмножество прежних. Таким образом, можно ипользовать эти модели, как критерий существенной новизны дополнительной информации о процессе: либо уменьшается число моделей (селективная информация) либо увеличивается "сложность" модели - минимально необходимое число элементов разбиения множества входных распределений (конструктивная информация).

5.1. Понятие частично определенного процесса. Терминология.

Определение. Выборкой процесса p на индукторном пространстве (T,I) назовем подмножество Q троек вида (t,x(:F{ t}), y(:F{ t}) ), обозначаемых далее (t,x,y), где y = p( x(:F{ t}, :F{ t}) для всех троек. Для данного элемента выборки t -центральная точка, x -входное распределение, y-выходное распределение. Если множество Q конечное, выборка называется конечной.

Частично определенный процесс - это множество всех процессов, имеющих указанные в выборке выходные распределения y для заданных в ней входных распределений x . При этом предполагаем заданными и одинаковыми для всех процессов множества входов X и значений ( далее "выходов") Y . Если процесс частично определен конечной выборкой, будем говорить о конечно-определенном процессе. Процесс удовлетворяет выборке, если он входит в частично определенный этой выборкой процесс. Автомат представляет выборку, если он представляет некоторый процесс, удовлетворяющий выборке.

Центральной выборкой CQ данной выборки Q назовем множество всех троек вида (t, x(:F{ t}), y ), обозначаемых далее [t,x,y], где y = p( x(:F{ t}, t) , для которых имеется тройка (e,z,q) О Q, такая, что t О F{ e}, z(:F{ t}) = x(:F{ t}), q(t) = y .

Пополненной выборкой SQ данной выборки Q назовем множество всех троек вида (t,x,y) для которых имеется (e,a,b) О Q, такой, что t О F{ e}, x = a(:F{ t}), y = b(:F{ t} .

Центральную и пополненную выборки будем называть порожденными выборками

Каждый элемент выборки порождает столько элементов порожденной выборки, сколько точек в полном индукторе центральной точки - носителе его распределений. Поскольку сама выборка по определению порождена некоторым процессом, то порожденные элементы не противоречат друг другу. Если полные индукторы центральных точек выборки на пространстве конечны, то конечной выборке соответствуют конечные порожденные выборки. В противном случае, обе порожденные выборки бесконечны. В частности, если все полные индукторы на пространстве конечны, как это имеет место, например, в дискретном времени, то конечные выбрки порождают конечные.

Общим рецептором выборки Q будем называть множество REC(Q) минимальных автоматов, ее представляющих. Автоматы из этого множества будем называть частными рецепторами В отличие от полностью определенных процессов частично определенные процессы могут иметь несколько или бесконечное число частных рецепторов.

Автомат конечен , если у него число состояний конечно и равномерно ограничено по всем точкам пространства. Если есть конечность числа состояний во всех точках, но без равномерного ограничения, то автомат назовем растущим. Эта терминология соответствует классической теории автоматов в дискретном времени.

5.2. Условия представимости выборки.

Определение. Два концентрических элемента пополненной выборки SQ несовместимы : (t,a,b)\not ~ (t,c,d), если найдется пара концентрических элементов той же выборки,
(e,x,y), (e,g,q), для которых t О F{ e} и (x = g)(:F{ e}\F{ t}), (x = a)(:F{ t}), (g = c)(:F{t}), но (y(e) № q(e)) . Здесь использованы распределния с булевскими значениями. Указанные элементы выборки с центром e назовем растром для данных несовместимых элементов.

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

Лемма. Автомат p представляет выборку Q тогда и только тогда, когда для каждой пары несовместимых элементов (t,a,b)\not ~ (t,c,d) с растром (e,x,y),(e,g,q) выполняется

(a) p(a,t) № p(c,t) при e = t .

Дополнительно выполняется требование: для любого элемента индукции (e,v) ~ I

(b) p(x,:Gv)И: a(:JvЗF{ t}) № p(g,:Gv) И: b(:JvЗF{ t})

Доказательство. Обозначим A функцию перехода, а f - функцию выхода автомата, W = JvЗF{ t}, E = Jv\W. Тогда для некоторого распределения z(:F{ e} \F{ t}) можно написать x = z И: a(:F{ t}); g = z И: c(:F{ t}) . Необходимость. Пусть p представляет Q. y(e) = fA(a(:W)И: z(:E) ,p(x,:Gv),e) , q(e) = fA(c(:W)И: z(:E) ,p(g,:Gv),e) . Поскольку эти выражения не равны, то получаем неравенства (b). В случае (a) fp(a,t) = y(e) № q(e) = fp(a,t). Достаточность. Если выборка для пары концентрических элементов дает разные значения в центре, то эти элементы несовместны и являются для самих себя растром. Поэтому, если выполнено условие (a) теоремы, то при входных распределениях, дающих по выборке разные значения процесса в некоторой точке e, автомат будет иметь разные состояния в этой точке. Таким образом можно определить функцию выхода на состояниях, дающую нужные значения процесса. ^[¯]

Следствие 1. Если входные распределения любых двух несовместимых элементов принадлежат разным состояниям автомата ("условие различимости"), то автомат представляет выборку. Это усиление условия (a) леммы. Необходимым это условие, вообще говоря, не является.

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

Теорема. На и-линейном пространстве условие различимости необходимо и достаточно для представления выборки автоматом. Доказательство. Осталось доказать необходимость. Если два несовместимых элемента выборки в точке t соответствуют одному состоянию s автомата p с функцией перехода A, то рассмотрим точку e из определения несовместимости на и-линейном пространстве. Если e = t, то y(e) = b(t),  q(e) = d(t), следовательно, b(t) № d(t), и входные распределения a и c не могут принадлежать одному состоянию автомата, представляющего выборку. Если e № t, то имеется соответствующий определению индуктор v, у которого в силу одноточечности границы Gv = { t} и по аксиоме границы F{ e}\F{ t} = Jv\F{ t} = Jv. Следовательно, x(:Jv) = g(:Jv), y(e) = A(x(:Jv), s, e) № A(g(:Jv), s, e) = q(e), что противоречит однозначности функции перехода. ^[¯]

5.3.Теорема. Конечная выборка может быть представлена конечным автоматом. Доказательство. Каждый автомат, представляющий выборку, может рассматриваться, как процесс, значения которого - это классы эквивалентности при некотором доопределении выборки до удовлетворяющего ей процесса. Для доказательства теоремы достаточно построить такое доопределение, при котором в каждой точке t будет конечное число классов эквивалентности на INPD(:F{ t}). Для произвольной выборки Q введем процесс

p[Q] = p[Q](x(:F{ t}),t) = y(t) если [x,y,t] О CQ;   = extern иначе;

где extern - дополнительный элемент множества значений выхода, не входящий в выходные распределения выборки Q. Это минимальный процесс, однозначно определяющий выборку. Поэтому любой автомат, представляющий данный процесс, будет представлять и выборку. Для построения автомата заметим, что если (t,x,y) элемент выборки, то для каждой точки e О F{t } пополненная выборка содержит (e,x(:F{ e}),y(:F{ e})), и, следовательно, если x(:F{ e}) не входит ни в какой элемент пополненной выборки с центральной точкой e, то никакое расширение этого распределения вида x(:F{ e}) И: x(:u) для какого-либо носителя u не может быть компонентой элемента выборки. Рассмотрим процесс r[Q](x(:F{ t}),t) = z(t) = x(:F{ t}) если $y: (x,y,t) О SQ;   = extern иначе. В силу вышесказанного, он представляет Q, а по аксиоме границы он является автоматом с функцией перехода

5.4. Если выборка представима конечным автоматом, то можно говорить о представляющих ее минимальных автоматах с минимальным числом состояний. Такие автоматы будем называть минирецепторами выборки Q и обозначать их множество mrec(Q). По определению mrec(Q) М REC(Q), но частные рецепторы могут иметь и большее число состояний (даже бесконечное).

5.4.1. Теорема. Если для выборки Q порожденные выборки конечны, то mrec(Q) не пусто и конечно. Доказательство. Если конечны порожденные выборки, то конечна и выборка. Непустота следует из наличия конечных представляющих автоматов у конечной выборки, а значит и конечных минимальных автоматов, поскольку при уменьшении автомата в структуре процессов уменьшается и множество его состояний, записанных в форме элементов разбиения входных распределений. Поскольку центральная выборка конечна, то конечны носители в каждом из элементов выборки, и, значит, конечная выборка использует только конечное число входных и выходных значений. Но тогда конечно множество всех возможных входных и выходных распределений на объединении всех носителей элементов выборки. Значит, конечно и множество всех возможных разбиений на входных распределениях. Тогда конечно множество всех представляющих выборку автоматов, в которых не увеличиваются множества значений входа и выхода. Множество mrec(Q) содержится в этом множестве.^[¯]

5.4.2. При бесконечных порожденных выборках конечной выборки возможно бесконечное mrec(Q). Пример. Рассмотрим бесконечный колчан с вершинами 0,1,2,ј и стрелами (i® 0),  i О { 1;2;ј} Выборка состоит из двух элементов : Q = { (0,1(:{ 1;ј} ),1(:{ 1;ј} ) ); (0,0(:{ 1;ј} ),0(:{ 1;ј} ) ) } , где использованы очевидные обозначения константных распределений. Если M М { 1;ј} , то выборку представляет автомат A[M] вида y(0) = min{ x(t) | t О M } ;   y(i) = x(i),  i = 1,ј;  X = Y = { 0;1} . При этом mrec(Q) = { A[{ i} ] | i = 1,ј; } . Число минирецепторов счетно. Причина этого в бесконечности полного индуктора точки 0.

6. Автоматы на однородных и-пространствах.

6.1. Определение. Индукторное пространство (T,I) однородно , если на нем транзитивно действует группа автоморфизмов G_T:

И-пространство (T,I) имеет однородное продолжение, если можно определить однородное пространство (T_g,I_g) со свойствами T М T_g, I М I_g, I_g/ T = I. (Использована операция переноса отношения индукции -п.1.3.5)

Многие, часто возникающие в теории и приложениях индукторные пространства, неоднородны, но имеют однородное продолжение. Например, дискретное время однородно продолжается до однородного линейного колчана (однородное дискретное время): ј® (-1)® (0)® (1)® ј. Аналогично, области линейных пространств продолжаются до всего пространства. В таких случаях на неоднородных пространствах можно определять однородные процессы, расширяя их определение на все продолжение.

Процесс однороден на однородном и-пространстве, если его значение инвариантно относительно действия транзитивной группы прстранства:

Замечание. Однородные процессы и автоматы достаточно определять только на концентрических индукторах: p(x(:F{ t })), A(x(:Jv), s(:Gv)) для фиксированного t О T, (t,v) ~ I , доопределяя на всех остальных по однородности автоморфизмами транзитивной группы:

e О T, he = t, h О GT , p(x(:F{ e }), e) = p(h*x); A(x(:Jv), s(:Gv), e) = A( h*x(:Jv), h*s(:Gv) ) .

6.2. Частично определенные однородные процессы.

Если известно, что процесс однороден, то имеющуюся в частичном определении выборку можно расширить по однородности до :

При подобном расширении выборки неоднородного процесса могут возникнуть противоречия типа (t,a,b),(t,a,d) О GQ;  b № d. Если выборка не порождает таких противоречий("квазиоднородность"), то ей удовлетворяет однородный процесс, независимо от однородности процесса, породившего выборку (неоднородность в выборке не проявилась). Тогда можно говорить о частично определенном однородном процессе.

Лемма. Пусть и-пространство (T,I) имеет однородное продолжение (T_g,I_g),t О T -выделенная точка, для каждого e О T  h[e] О G_Tg, h[e]e = t . Тогда, если выборка Q на T имеет множество центров индукции элементов M М T, входной алфавит X, и обладает свойством

# X ^D і # Q , где D = { F_g{ t } \ (Иh[e]F{ e}|e О M)} , то входные и выходные распределения элементов выборки можно так доопределить на всех F_g{ e} \F{ e}, e О M , что получится квазиоднородная выборка Q_g. Доказательство. Условие на выборку позволяет так доопределить распределения элементов выборки, что после сдвигов в выделенную точку никакие два элемента не будут иметь одинаковые входные распределения. Для этого достаточно задать разные входные распределения x_z(:D) для всех z О Q, произвольно доопределить x_z(:F{ t } \h[e]F{ e } \D ), и выходное распределение y_z(:F{ t } \h[e]F{ e } ), где e -центр индукции элемента z = (e,x,y), после чего построить новый элемент для выборки Q_g на однородном расширении z_g = (e, h[e]^-1x_zИ: x,   h[e]^-1y_z И:y ). По построению, такая выборка не порождает противоречий при однородном расширении, т.е. является квазиоднородной.^[¯]

Такую выборку Q_g будем называть квазиоднородной модификацией выборки Q.

Замечание. Если и-пространство (T,I) имеет однородное продолжение (T_g,I_g) , то для любой выборки с неодноэлементным множеством входов на этом пространстве можно построить такое однородное продолжение, которое удовлетворяет условию леммы, и, следовательно, на нем эта выборка будет иметь квазиоднородную модификацию. Для доказательства введем множество W равномощное множеству элементов выборки. Построим новое множество точек B = T_g×W на котором введем отношение индукции

Однако для некоторых однородных продолжений это требование межет и не выполняться. В практически важных случаях дискретного времени, полупрямой и направленной полупрямой на естественных однородных продолжениях до однородного линейного колчана, полной прямой и полной направлнной прямой соответственно все конечные выборки удовлетворяют условию леммы, поскольку # D = Ґ. Поэтому классическая теория автоматов была развита для однородных по времени матриц и функций перехода.

6.3. Построение однородного рецептора конечной выборки.

Для случая дискретного времени задача вычисления однородных минирецепрторов конечной выборки решается алгоритмически. Следуя традиции, будем называть распределения на отрезках дискретного времени со значениями в конечном алфавите "словами". Поскольку все полные индукторы в дискретном времени конечны, то конечная выборка состоит из конечных входных и выходных слов, а множества входов и значений можно считать конечными алфавитами. Полный индуктор любой точки t имеет вид { 0,1,ј,t } и элемент выборки имеет вид (t, x₀јx_t, y₀јy_t). Значение y_t назовем выходом (входного) слова x.

6.3.1. Процедура последовательного разбиения (ППР).

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

(0) Все входные слова выборки нумеруются в произвольном порядке. На этом этапе ни одно слово еще не отнесено к классу. Для каждого входного слова запоминаются номера тех слов, с которыми оно не совместимо в смысле принадлежности к несовместимым элементам выборки (п.5.2). Это означает, что у несовместимых слов имеются одинаковые продолжения , принадлежащие пополненной выборке и имеющие разные выходы. (1) Выбирается первое слово, еще не отнесенное к какому-либо классу. Слово относится к первому уже созданному классу, в котором нет несовместимых с ним слов. Если такого класса нет, то вводится новый класс с очередным порядковым номером, и слово относится к нему. (2) После отнесения слова к классу к выборке добавляются вторичные элементы, полученные добавлением к каждому слову этого класса всех продолжений, которые имеют в выборке другие слова этого класса. В качестве выходного слова на продолжении задается то выходное слово, которое указано в элементе, откуда взято продолжение. Отбрасываются повторно возникающие элементы выборки. В силу определения совместимости слов (п.5.2) противоречий при таком расширении выборки возникнуть не может. (3) Для всех первичных элементов выборки переопределяется таблица несовместимости с учетом вторичных элементов. Могут возникнуть новые несовместимости, но построенные классы при этом не разрушаются. (4) Шаги (1)(2)(3) повторяются для всех первичных элементов выборки.

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

6.3.2. Построение мини-рецептора выборки.

Определение. Входное слово из выборки назовем оконечным, если выборка не содержит входного слова, его продолжающего. Выборку назовем полной, если: a) она содержит пустое слово; b) для любого неоконечного слова она содержит все возможные продолжения на один символ входного алфавита; c) выход в каждом оконечном слове совпадает с выходом в каком-либо неоконечном слове.

Теорема.Любое последовательное разбиение полной выборки определяет отображение перехода однородного автомата, состояниями которого являются введенные классы, и который является рецепторм выборки. В частности, если число классов конечно (например, если выборка конечна) то и автомат конечен Доказательство. Введение вторичных элементов выборки обеспечивает следующие свойства. 1) На каждом шаге, если q,b,e слова и q,b лежат в одном классе, а e совместимо с q, то e совместимо с b ( поскольку у всех слов, отнесенных к одному классу одинаковый набор продолжений и выходов на этих продолжениях). 2) Если в конце процдуры разбиения два слова совместимы, то они были совместимы на всех шагах ( поскольку множество вторичных элементов, а значит и возможных продолжений, только растет по шагам). Следствие. Если в конце ППР два слова совместимы, то они отнесены к одному классу: первому, в порядке возникновения, совместимому с первым из этих слов. Такими образом, полученное разбиение минимально, и, если в одном классе разбиения имеются неоконечные слова a₁јa_n, b₁јb_m то в одном классе окажутся и слова a₁јa_nx, b₁јb_mx где x любой элемент входного алфавита. Оконечное слово по той же причине входит в тот класс, куда вошло одно из слов с тем же выходом (эквивалентность по пустому продолжению). В результате, если выборка полная, то для каждого класса однозначо определен переход в другой класс при продолжении любого его слова произвольным (фиксированным) входным символом. Это определяет однородный автомат в дискретном времени (по группе сдвигов минимального однородного продолжения), где состояниями являются классы разбиения. По тореме п.5.2 он представляет выборку. В силу доказанной минимальности разбиения он мини-рецептор. ^[¯]

Замечание. Если выборка не полная, то в полученных классах возможно будут отсутствовать указания на переходы в другой класс при некоторых входных символах. Их можно дополнить произвольно, получив полную матрицу переходов автомата. Поскольку минимальность разбиения при этом не нарушается, то при каждом доопределении переходов будет получаться новый мини-рецептор. Утверждать, что так будут перебраны все мини-рецепторы нельзя, поскольку полученное множество состояний ( разбиение входных слов выборки) зависит от исходной нумерации слов, и при каких-то нумерациях могут быть получены другие автоматы. Однако можно утверждать, что перебор некоторых параметров ППР даст все минирецепторы конечной выборки.

6.3.3. Построение mrec выборки.

Теорема.Все минирецепторы конечной выборки и только их можно получить из ППР, варьируя: 1)начальную нумерацию элементов выборки ( подшаг 0 ); 2)выбор класса, куда можно отнести очередное слово (подшаг 1); 3)дополнительные переходы в неполном графе переходов на классах, если выборка не полная (по окончании ППР). Такую процедуру назовем вариационной ППР (ВППР) .

Доказательство. Из теоремы п.6.3.2 следует, что при любом выборе указанных параметров будет получаться минирецептор. Допустим имеется некоторый минирецептор выборки Q с состояниями s₁јs_m. Тогда каждому состоянию s_i соответствуют некоторые входные слова из выборки x_i,1јx_i,k(i), которые переводят минирецептор в это состояние. В силу минимальности автомата, каждый такой класс слов содержит хотябы одно слово, несовместимое со всеми другими классами - иначе слова из этого класса можно распределить по другим классам, и уменьшить общее число состояний. Пронумеруем Q так, чтобы такое слово было первым в каждом классе. Этого можно добиться, поместив эти элементы выборки впереди в порядке роста номера состояния. При такой нумерации выборки ВППР на каждом шаге допускает отнесение очередного входного слова к его состоянию рассматривоемого рецептора. Значит этот рецептор может быть получен вариацией (2) на подшаге 1 при соответствующем доопределении недостающих переходов в конце ППР. ^[¯]

6.3.4. Примеры применения ППР.

За возможность построения множества мини-рецепторов приходится платить значительным увеличением объема вычислений ВППР для каждого автомата по сравнению с ППР. Это обусловлено сложностью вариационного выбора класса на подшаге 1. Однако вариация отнесения входного слова к одному из классов и вариация дополнительных переходов после разбиения выборки на состояния неизбежны при любом способе решения этой задачи. Во многих прикладных задачах можно ограничиться получением мини-рецептора, не осуществляя значительного перебора по их множеству с целью абсолютной оптимизации по какому-либо дополнительному критерию. В такой ситуации достаточно применить ППР для нескольких нумераций выборки и выбрать один из результатов. Так, например, была оптимизирована технологическая программа  [5] , и получен значительный эффект по уменьшению объема программы. В качестве выборки использовались данные технологической инструкции и наблюдений за объектом в нештатных ситуациях. Опыт использования ППР показал, что это нужное дополнение к вероятностной статистике, позволяющее эффективно моделировать ту компоненту данных наблюдений и описаний динамики объекта математического моделирования, которая представляется не случайной.

Ниже будут приведены два примера применения алгоритма в упрощенных ситуациях с целью демонстрации вычислительной схемы. Использованы следующие обозначения: * - пустое слово длины 0; . - неизвестный выход на слове; нумерация слов в таблице соответствует использованной в ППР; вторичные слова нумеруются номером шага, где они возникли, и буквой в порядке заведения в таблицу; выходы вторичных продолжений слов помечаются штрихом; классы слов обозначаются буквами.

6.3.4.1. Пример ППР для неполной выборки .

Таблица наблюдений:

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

            ? a a a b        -выходы
            E A B C D  ?     -состояния
          E   0 1
          A     0 1          -переходы состояний
          B       0    1      при входах 0/1
          C         0  1        ? - неопределенность
          D         0  1

 

6.3.4.2. Пример ППР для полной выборки .

Таблица наблюдений.

  время    012   12   1
  входы    *00   01   1
  выходы   aba   bb   a

Расчетная таблица ППД.

 #  слово        продолжение слова/выход              класс
    x              *         0  1  00  01
 1  *              a         b  a  a   b               A
 2  0              b         a  b  .   .               B
 3  1              a         b' a' a'  b'              A
 3a 10             b
 3b 11             a
 3c 100            a
 4  00             a         b' a' a'  b'              A
 4a 000            b
 4b 001            a
 4c 0000           a
 4d 0001           b
 5  01             b         a' b'                     B
 5a 010            a
 5b 011            b
 

Этому разбиению соответствует матрица переходов автомата-тригера:

           a   b      -выходы
           A   B      -состояния
        A  1   0      переходы состояний
        B  0   1      при входах 0/1

7.Индукторные изображения групп.

7.1. Определения. Понятие индукторного изображения.

Гомеоморфизм g:(A,I)® (B,K) индукторного пространства (A ,I ) в И-пространство (B,K) - это биекция g:A « C, C М B , такое ,что (t,v) ~ I Ы (gt,gv) ~ K/ C . Гомеоморфизм на себя назовем автоморфизмом. Обозначение: aut(T,I) - группа автоморфизмов и-пространства (T,I); Пространства изоморфны, если имеется гомеоморфизм одного на другое (изоморфизм пространств).

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

Если группа G действует на некотором индукторном пространстве (A,I), как подгруппа out(A,I), то И-пространство (B,K) изображает это действие, если (B,K) является изображением G и имеется гомеоморфизм Q:(A,I)® (B,K), при котором действие группы на A переходит в ее действие на QA.

7.2. Теорема существования изображения действия группы.

7.2.1.Определение. Индукторное пространство называется жестким, если оно изображает единичную группу, т.е. не имеет автоморфизмов кроме тождественного.

Лемма. Для любой мощности M существует множество мощности 2^М попарно неизоморфных связных жестких индукторных пространств мощности М каждое. Эти пространства можно построить так, что у каждого будет ровно одна точка, полный индуктор которой совпадает со всем пространством, а остальные полные индукторы точек вполне упорядочены в структуре подмножеств.

Доказательство. Рассмотрим произвольный порядковый тип h мощности М. Колчаном порядкогого типа r(h+1) назовем множество вершин { x | x < h } со стрелами { (x ® y) | x < y }. Покажем, что это - жесткое И-пространство. При любом автоморфизме f точка "1" переходот в себя, т.к. нет других точек без входящих стрел от других точек. Трансфинитная индукция. Допустим при f неподвижны все x < y. Тогда точка y - единственная точка из множества Z = z| z > y,которая не получает входной стрелы из Z \{ y} . Следовательно, при f(z) = y, z > y, найдется точка u > y, u < z, для которой f(u) = x < y . Но тогда f(x) № x, что противоречит предположению индукции. Следовательно, f(y) = y. Индукция завершена. Заметим, что в доказательстве жесткости нигде не использовано наличие или отсутствие стрелы (y® y) из точки на себя (петли). Задав такие стрелы на произвольном подмножестве A из r(h), мы получим новый жесткий колчан r(h,A). При разных A такие И-пространства не изоморфны , т.к. в силу жесткости при любом гомеоморфизме подможество A переходит в свою копию на другом колчане, но при разных A это не возможно: не совпадут петли. Если h предельный тип, то перейдя к h+1 мы получим максимальный элемент без измемнения мощности M. ^[¯] Минимальный элемент колчана w типа r(h,A) далее будем обозначать 1w, а максимальный hw.

7.2.2. Теорема. Любое действие группы на индукторном пространстве имеет изображение. Доказательство. Пусть G:(T,I) - действие группы G ~ Н aut(T,I) на И-пространстве (T,I) . Строим множество W = T\sqcup G×T = T×({ 0} \sqcup G ), где \sqcup -объединение непересекающихся множеств. Строим индукцию J на W. На 0×T задаем I, т.е. ((0,t),(0,v)) ~ J Ы (t,v) ~ I . На G×T зададим J = A×B, где индукция A -любая жесткая индукция на каждом (g,T) М G×T, g О G. Индукция B порождена графом {(0,gt)® (g,t)| g О G, t О T } . Требуем, чтобы индукция A была связной и отличной от I. Это всегда можно сделать по лемме 7.2.1. Тогда aut(W,J) ~ G , и каждый g О G действует на (0×T) также, как на (T,I). Докажем это. Для перенесенной индукции (п.1.3.5) имеет место: J/ (0,T) = I;  J/ (0,T) М J . Пусть e -единица группы G. Если h О aut(W,J) & h(e,t) = (g,p) то из A № I следует g № 0, g О G . При автоморфизме сохраняется свойство жесткости пренесенной индукции на любом подмножестве, где оно имело место. J/(g,T) = A. Всилу жесткости A и изолированности подмножеств (g,T), (q,T) при g № q в перенесенной индукции J/ G×T получаем h(e,T) = (g,T). По построению B имеется (0,t)® (e,t). Поэтому h(0,t)® h(e,t) т. е. h(0,t)® (g,t), откуда h(0,t) = (0,gt). Обратно, каждому g О G соответствует h О aut(W,J) с условием h(e,t) = (g,t), t О T. Следовательно, построено изображение действия группы.^[¯]

7.2.3. Следствие. Каждая группа имеет изображение. Если на группе задана индукция, то имеется изображение, подмножество которого гомеоморфно группе, и действие группы на нем соответствует действию группы на себе. Достаточно в теореме рассмотреть T = G. Такие изображения будем называть инъективными.

7.3. Понятие индукторной группы.

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

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

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

Группа называется индукторной, если на ней задана идукция, как на множестве точек, и групповая операция по обоим операндам является автоморфизмом этого И-пространства.

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

7.3.2. Лемма. О соотношениях сходимости.
a) Гомеоморфизм индукторных пространств является гомеоморфизмом любого подмножества на его образ в перенесенной индукции.
b) Сходимость последовательности точек на подмножестве в перенесенной индукции эквивалентна ее сходимости в полной индукции во всем индукторном пространстве к той же точке.
c) Если на пространстве задано две индукции, причем в каждом индукторе некоторой точки в первой индукции содержится индуктор той же точки во второй индукции, то сходимость к этой точке во второй индукции влечет сходимость и в первой. Следствие: если на множестве точек задано две индукции, и в каждом индукторе любой точки в любой из этих индукций содержится ее индуктор в другой индукции, то эти индукции на пространстве эквивалентны по сходимости .
d) Гомеморфизм по индукции влечет и гомеоморфизм по сходимости.
e) Возможен гомеоморфизм по сходимости между негомеоморфными индукторными пространствами.
f) Объединение индукторов и-отношений слабее по сходимости каждого из исходных отношений.
g) Объединение индукторов и-пространств (T,I), (T,Iў) слабее по сходимости каждого из пространств, если оператор {uit}(I*Iў) (в обозначениях п.1.3.1) не нарушает аксиому границы.

Утверждения (a)(b)(c)(d)(f) следуют непосредственно из определений. Пример (e). Зададим две индукции на числовой прямой. В первой, индукторы точки - это все замкнутые интервалы , для которых она - внутренняя. Во второй, индукторами точки являются замыкания всех открытых множеств, содержащих ее. Эти индукции не гомеоморфны : вторая содержит несвязные индукторы, а первая - только отрезки. Но по сходимости они эквивалентны в любой точке обычной топологии интервалов.)

Доказательство (g). По (c) достаточно показать, что в каждом индукторе объединения Iўў = I\odot Iў (п.п. 1.3.3, 1.3.1) содержится индуктор каждой из исходных индукций I и Iў для той же точки пространства T. Для системы индукторов объединения { (t,v Иw) ~ Iўў[0] | (t,v) ~ I, (t,w) ~ Iў, t О T} это так. Индукция. Пусть это верно для Iўў[n], полученного из I,Iў не более чем n объединениями и пересечениями по аксиомам индукции. Тогда по (c) это верно и для { (t,A ИB) ~ Io[n+1] | (t,A) ~ Iўў[n],  (tў,B) ~ Iўў[n], t О T, tў О JA } . Строим { (t,AЗB) ~ Iўў[n+1]| (t,A) ~ Io[n+1], (t,B) ~ Io[n+1], t О T }. Для каждого (t, C) ~ I"[n+1],  C = AЗB, имеется, по предположению индукции, (t,v) ~ I, v О A, и (t,w) ~ I, w О B . По аксиоме пересечения для I получаем (t,vЗw) ~ I, но vИw О C. Аналогично построение для Iў(tў). Индукция завершена. Таким образом, операторы u,i,t операции space не усиливают сходимость на пространстве. Оператор e не применяется, поскольку индукции удовлетворяют аксиоме включения. По условию (g) в операции space при построении объединения индукций не применяется оператор b. ^[¯] Замечание.Нарушение аксиомы границы на промежуточных стадиях операции space I*Iў возможно. В этом случае возникают петлевые точки, дискретные (наиболее сильные) по сходимости.

7.3.3.Определение. Индукция ортогональна к подмножеству пространства в некоторой его точке, если пересечение любого индуктора этой точки с подмножеством содержит только эту точку, и она не петлевая. Индукция параллельна подмножеству в его точке, если любой индуктор этой точки содержится в подмножестве. Две индукции взаимно-ортогональны, если каждая из них ортогональна любому индуктору другой в любой его точке.

Лемма.Если на пространстве задано объединение двух взаимно -ортогональных индукций I и Iў, непустых в каждой точке, то в каждом индукторе все точки, кроме центра, граничные. Следствие: Если одна из этих индукций параллельна подмножеству S , а другая ортогональна S , то на S перенесенная индукция совпадает с параллельной. Доказательство. Пусть индуктор имеет вид C = AИB, A О I(t), B О Iў(t), t О T. В силу взаимной ортогональности, ни одна точка A\t(B\t) не имеет внутри C своего Iў индуктора (I- индуктора ). Следовательно GC = C\t относительно индукции I*Iў. Но тогда аксиомы объединения и пересечения не порождают индукторов, кроме рассмотренных выше. Если S параллельно I, то на S индукторы типа С порождают перенесенную индукцию I. ^[¯]

7.3.4. Теорема.Любое действие индукторной группы на индукторном пространстве имеет топическое изображение.
Доказательство. Рассмотрим индукторную группу (G,K) с индукцией K, действующую на И-пространстве (T,I), как подгруппа автоморфизмов: (G,K):(T,I);  (G,K) М aut(T,I). Индукция K согласована по сходимости с действием: lim g_i = g (mod K) Ы "t О T   lim g_it = gt (mod I). Построим инъективное топическое изображение этого действия. W = (G \sqcup { 0 } ) ×(T \sqcup { 0 } ) Введем несколько индукций, из которых будет построена искомая индукция на W. На 0×T индукция I аналогична (T,I): ((0×t),(0×v)) ~ I Ы (t,v) ~ I. На всех g×T, g О G задаем жесткую индукцию A, аналогичную (T,A). На G×0 индукция K аналогична (G,K). На G×T -индукция D: (g,v) ~ K Ы (def) ((g×t),(v×t)) ~ D . На W - индукция B = { (g×t, { g×t;  0×gt }) ~ B ~ g О G, t О T }. На W -индукция C = { (g×t, { g×t; g×0 }) ~ B | g О G, t О T }. Необходимая индукция на W строится по формуле P = D*C*A*I*B*K . Покажем, что (W,P) -индукторное пространство. На G×0 и 0×T аксиомы выполнены по построению, поскольку на этих подмножествах P совпадает с K и I соответственно. На G×T индуктор точки g×t имеет вид: (g×t , {g×t; 0×gt; g×0}И g×v Иu×t ) ~ P, где (t,v) ~ A,  (g,u) ~ K. Все объединяемые индукции взаимно- ортогональны в совокупности. По лемме 7.3.3 в каждом индукторе все точки, кроме центра, граничные, и каждая из индукций удовлетворяет всем аксиомам. Следовательно, оператор space не породит новых индукторов. По лемме 7.3.2(g) сходимость на (G×T,P) не сильнее сходимости в D. Построенное пространство является изображением группы G, поскольку индукция C допускает только такие автоморфизмы, при которых слой g×T переходит в слой того же типа. Дальнейшее доказательство наличия изображения повторяет доказательство теоремы 7.2.2. Допустим lim g_i = g (mod K). При любом автоморфизме слоев индукция A допускает только тождественное отображение компоненты T. Тогда получаем ("q О G, t О T) lim g_i(q×t) = g×t (mod P),   lim g_i(q×0) = g×0 (mod P) . Из согласованоости индукций K,I следует lim g_i(0×t) = 0×gt (mod P) . Это означает топичность изображения. ^[¯]

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

8. Нечеткие индукторные пространства.

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

8.1. Нечеткие множества с нечеткими подмножествами.

Определение. Нечетким множеством называется триада M = fuzzy[S,W,P], где S = pel(M) - множество потенциальных элементов нечеткого множества; W = wset(M) -частично упорядоченное множество значений весов; P = wcor(M) -весовое соответствие, сопоставляющее каждому подмножеству потенциальных элементов его вес. P: bool(S)® W . Выполняются следующие условия.

1) W К DUO = { DETERM; UNDEF; OUT },   OUT < UNDEF < DETERM .

2) Все веса сравнимы с OUT и DETERM, причем OUT = min W; DETERM = max W; UNDEF несравним с W\DUO.

3) B Н A Н S Ю P(A) \not > P(B).

4) P(Ж) = DETERM .

5) P(A) = P(B) = DETERM Ю P( A ИB ) = P( A ЗB ) = P( A \B ) = DETERM Объединения любой совокупности множеств веса DETERM имеют тот же вес.

8.1.1. Стандартная интерпретация введенных понятий.

Вес DETERM интерпретируется, как детерминированное вхождение подмножества в состав подмножеств нечеткого множества. Вес OUT - детерминированное невхождение подмножества в состав подмножеств. Детерминированные веса соответствуют четким характеристикам. Из свойства 2 следует, что других минимальных и максимальных весов нет. Множество четкое, если вес каждого элемента из S детерминированный. Такие множества содержат с весом DETERM все подмножества DETERM -носителя на S (по свойствам 5, 3). Вес UNDEF -полная неопределенность принадлежности подмножества к множеству. Веса из W\DUO означают известную, но не детерминированную принадлежность подмножества к множеству. Свойство 3 допускает несравнимость весов подмножеств A,B.

8.1.2. Случайные множества.

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

Определение. Случайным множеством M = fuzzi[S,W,P] назовем следующую конструкцию нечеткого множества. W = DUOИ[0;1]; 0 = OUT; 1 = DETERM . E -множество элементарных событий с s -алгеброй подмножеств H и вероятностной мерой prob на ней. Каждому e О E сопоставим D(e) Н S;  D:E®bool(S) . Каждому подмножеству A Н S сопоставим событие ev(A) = { e | A Н D(e) } и вес P(A) = ( prob(ev(A)) если ev(A) О H;  UNDEF иначе ).

8.2. Нечеткие отношения индукции.

Отношение индукции на множестве точек T введено, как подмножество I Н S[T] = T×bool(T). Нечеткое отношение индукции введем, как нечеткое множество с pel(M) = S[T]. Для дальнейшего потребуется частный случай таких отношений, использующих четкие индукции.

8.2.1. Определение. Смесью отношений индукции из множества { A_j | j О Q } с коэффициентами C_j из частично -упорядоченного множества весов W на множестве точек T назовем нечеткое отношение индукции, обозначаемое

Смесь индукций - если все отношения в смеси ( кроме S[T]) являются индукциями. Нечеткая индукция M и нечеткое индукторное пространство (T,M) - это нечеткое отношение индукции, P = wcor(M), удовлетворяющее аксиоме: если И-отношение V Н space(V), то P(V) = P(space(V)) , иначе P(V) = UNDEF.

Замечание. В альтернативной смеси вес UNDEF не возможен: если Z не является подотношением ни одного из A_j, то Z Н S[T] и поэтому P(Z) = OUT .

8.2.2. Лемма. Пусть Z И-отношение. Тогда, если Z Н I для некоторой индукции I, то Z Н space(Z) . Кроме того space(Z) = ЗI | Z Н I . Доказательство. Если Z Н I , то в Z выполняется аксиома принадлежности. Тогда space(Z) = { uibt } eZ = { uibt }Z . Операторы u, i, b, t не устраняют из И-отношения индукторов, следовательно Z Н space(Z) . Поскольку И-отношение не содержит индукторов, не входящих в индукцию I, то Gv (mod I) Н Gv (mod Z);    Fv (mod Z) Н Fv (mod I) для любого v Н T . Следовательно, аксиома границы для Z выполняется. Таким образом, (uibt)Z = (uit)Z; . С другой стороны, поскольку индукция удовлетворяет аксиомам объединения и пересечения, (uit)Z Н I , что по индукции дает "n  (uit)ⁿ Z Н I;   space(Z) = uitZ = (И(uit)ⁿ Z | n = 1ј) Н I; В силу произвольности индукции I и того, что space(Z) -индукция, доказано второе уравнение леммы. ^[¯]

8.2.3.Теорема. Любая нечеткая индукция является смесью четких индукций и обратно. Доказательство. Пусть в нечеткой индукции M, P = wcor(M), И-отношение Z имеет вес P(Z) = UNDEF. Тогда либо P(space(Z)) = UNDEF по аксиоме нечеткой индукции, либо, по лемме, такое И-отношение не содержится ни в одной индукции. По аксиоматике нечеткого множества вес любой индукции, содержащей Z, либо UNDEF либо OUT. Для произвольного отношения индукции Z: P(Z) № UNDEF по лемме P(Z) = space( P(Z)) = max{ P(I) | Z Н I }. Но тогда выполняется определение смеси индукций: M = mix( P(I).I | I = space(I) ) . В такой форме можно представить любую смесь индукций. Пусть задана такая смесь. Тогда для любого И-отношения P(Z) = max{ P(I) | I = space(I), Z Н I } or UNDEF if Z\not Н space(Z) . При Z Н spase(Z) по лемме space(Z) = min { I | I = space(I), Z Н I }, и по определению смеси P(Z) = P(space(Z) ; следовательно M -нечеткая индукция. ^[¯]

8.2.4. Определение. Вероятностная смесь отношений индукции A₁,ј, A_n -это смесь M с wset(M) = DUO И[0;1], OUT = 0, DETERM = 1, коэффициенты смеси: p₁,ј, p_n ;  p_i О [0;1];   p₁+ј+ p_n = 1; смесь определена уравнением: prmix(p₁.A₁,ј,p_n.A_n) = altmix((p_j1+ј+p_jk). (A_j1ЗјЗA_jk) | J = {j₁;ј;j_k} Н { 1;ј;n } &  # ( J) = k;  k = 1,ј,n ).

Такое определение соответствует случайной реализации однго из A_i с вероятностью p_i, причем вес любого И-отношения равен вероятности реализации содержащего его A_i. Если эти отношения являются индукциями, то и их пересечения тоже индукции, поскольку все аксиомы индукторного пространства выдерживают операцию пересечения. В этом случае можно говорить о случайной индукции.

8.3. Изоморфизм нечетких индукций.

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

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

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

8.3.2. Теорема.Двухкомпонентные вероятностные смеси неизоморфных индукций с различными коэффициентами не изоморфны. При изоморфных несовпадающих индукциях изоморфны только смеси с дополнительными (или совпадающими) вероятностными коэффициенам. При совпадении индукций изоморфны все вероятностные смеси. Доказательство. В соответствии с леммой 8.3.1. две смеси неизоморфных индукций X и Y , Z = X ЗY , prmix(a.X, (1-a).Y) = mix(a.X, 1.Z, (1-a).Y, 0.S[T] ) , prmix(b.X, (1-b).Y) = mix(b.X, 1.Z, (1-b).Y, 0.S[T] ) , могут быть изоморфны только либо при b = a либо b = 1-a. В условиях теоремы остается второй случай, причем a и 1-a различны. Если смеси имеют изоморфизм f, то он порожден отображением g:T « T, и поэтому каждый индуктор имеет ровно один образ, не зависимо от того, во сколько индукций он входит. Следовательно, fZ = Z. Равенство весов отношений индукции, f-образа и прообраза, требует f(X\Y) = (X\Y). Но тогда f устанавливает изоморфизм X и Y. Если изоморфизма индукций нет, то невозможен изоморфизм смесей. Если индукции совпадают, то изоморфизм устанавливается тождественным отображением. prmix(a.X, (1-a).Y) = mix( 1.Z, 0.S[T]) = prmix(b.X, (1-b).Y). ^[¯]

8.4. Деформация И-пространств.

Определение. Непрерывная деформация индукторных пространств - это множество вероятностных смесей { Е(a) = prmix( a.I, (1-a).Y ) | 0 Ј a Ј 1 } .

Оно интерпретируется, как траектория непрерывного перехода И-пространства (T,I) в И-пространство (T,Y). Теорема 8.3.2 показывает, что при неизоморфных индукциях все точки этой траектории различны, а при изоморфности несовпадающих индукций неизоморфны достаточно близкие точки. Непрерывность интерпретируется, как непрерывное изменение Е(a) по параметру a в топологии объемлющей алгебры ALI(I,Y;R) действительных функций на отношениях индукции, содержащихся в (I ИY). Можно рассмотреть и более широкую алгебру ALI( S(T); R). Значение функции интерпретируется, как вес И-отношения. При этом возможен непрерывный переход между любыми двумя индукциями. В частности, можно говорить о непрерывном переводе одной группы в другую путем деформации их изображений .

8.4.1. Комплекс нечетких индукций.

Непрерывные деформации позволяют рассматривать множество индукций на одном множестве точек, как вершины симплекса с одномерными ребрами между любыми двумя вершинами. Вероятностные смеси трех неизоморфных индукций в этом случае оказываются двухмерными гранями, а вероятностные смеси N неизоморфных индукций - N-1-мерными гранями. Возникает комплекс нечетких И-пространств. Этот комплекс обладает дополнительной структурой по вложенности индукций, которой соответствует частичная упорядоченность вершин. Не известно, можно ли указать непосредственные миноранты и мажоранты любой индукции. Минимальным элементом структуры является пустая индукция {(t,v) ~ I | t О T } = Ж, максимальный элемент - максимальная индукция

Imax[T] = { (t,v) | t О T, v Н T , t О v }.

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

9. Нечеткие изображения групп.

Определение. Нечеткое индукторное пространство изображает группу, если она изоморфна группе его автоморфизмов.

9.1. Теорема.Группа автоморфизмов нечеткой смеси И-пространств
aut mix( a₁.I₁,ј, a_n.I_n ) = ( Зaut I_j| j = 1,...,n ) И ( И[ ( Зmor(I_i,I_j) | (i,j) О M ) З ( Зaut I_k| k О N(M) ) ] | M О Q ) ,
где Q - множество всех наборов М пар (i,j): a_i = a_j,I_i ~ I_j ( гомеоморфны), N(M) : множество k, не входящих в пары (k,j) из M ; mor(I,Iў) -множество изоморфизмов I на Iў.

Доказательство. Первая скобка правой части равенства выражает множество всех отображений, являющихся автоморфизмами всех индукций. Вторая скобка объединяет отображения, которые для некоторых индукций являются автоморфизмами, а для остальных - изоморфизмами в другие индукции, имеющие тот же вес. Множество изоморфизмов определяется набором пар M. Для каждого M возможные отображения выражены квадратной скобкой. Каждое отображение из построенного множества является автоморфизмом смеси. Автоморфизм смеси переводит каждую индукцию в изоморфную индукцию, и не порождает новых индукций. Это означает, что каждая индукция переходит либо в себя автоморфно, либо в другую индукцию из смеси, имеющую тот же вес. Поскольку параметр M в формуле пробегает все возможные такие комбинации, то любой автоморфизм входит в построенное множество. ^[¯]

9.2. Теорема. При непрерывной деформации E(a) одного индукторного пространства I в другое Y группа автоморфизмов меняется дискретно по параметру a:

aut prmix(a.I,(1-a)Y) = aut(I) если a = 1 ;
или aut(I) Зaut(Y) если 0 < a < 1/2, 1/2 < a < 1;
или aut(I) Зaut(Y) если a = 1/2, I \not ~ Y ;
или ( aut(I) Зaut(Y) ) И ( mor(I,Y) Зaut(Y) ) И ( mor(Y,I) Зaut(I) ) И ( mor(I,Y) Зmor(Y,I) ) если a = 1/2, I ~ Y ;
или aut(Y) если a = 0;

Эта теорема является следствием теоремы 9.1 : приведенные значения группы автоморфизмов получены применением общей формулы для автоморфизмов парных смесей. При неизоморфных индукциях для промежуточных значений параметра 0 < a < 1 изображаемая группа является подгруппой обеих групп, изображаемых в крайних положениях. При изоморфизме индукций без их совпадения группа возвращается к исходной (изоморфной), пройдя преобразования при a = 1,  1/2,  0 . При совпадении индукций группа не меняется.^[¯]

10. Алгебры, связанные с индукциями.

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

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

Это соответствует идее квантования групп через алгебры Хопфа, развиваемой рядом авторов  [6] [7] [8] . Однако в данном подходе уместнее говорить о квантовании действия группы, поскольку индукторное пространство определяет группу ее действием на этом пространстве.

10.1. Определение индукторной алгебры.

Отношению индукции I сопоставим градуированную алгебру A над действительными числами с образующими { (a,v) |(a,v) ~ I } и формальными коммутативными линейными комбинациями c₁(a₁,v₁)+ј+c_n(a_n,v_n) где c_i -числовые коэффициенты. Умножение определено формулой

(a,v)*(b,w) = L₁(a,v) + L₂(b,w) где L₁, L₂ - параметры умножения (числа).

На линейные комбинации умножение распростаняется по дистрибутивности. Таким образом, элементы алгебры A - это линейные комбинации.

Введем градации элементов алгебры: X = { 0;1;2} . Элементы градуированной алгебры имеют вид e.[x] где e О A; x О X . Операции определены формулами:

e.[x] + u.[y] = (e + u).[max(x;y)] ; e.[x] *u.[y] = (e *u).[max(x;y;g)]

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

g( (a,v)*(b,w) ) = 0 если (a = b) или 1 если (b О v) или 2 ;
g( (c₁e₁+ј+c_ne_n)* (d₁u₁+ј+d_mu_m) ) = { g(e_i*u_j) | i = 1јn;j = 1јm } ,

где e_i, u_j -образующие. Эту конструкцию назовем алгеброй индукторов или И-алгеброй Ialg(T,I) для И-пространства (T,I).

Если исходные данные для И- формулы имели ранг 0, то в результате .[0] означает, что все умножения проводились на концентрических парах индукторов; .[2] означает, что в одном из умножений центр правого сомножителя лежал вне индуктора левого; .[1] означает, что были неконцентрические умножения, но все ценры правых сомножителей лежали в индукторах левых. Введем обозначения. rnk(x) - ранг элемента x из Ialg(T,I); cen(x) - множество центров в слагаемых x ; ind(x) - множество индукторов в слагаемых x. Выражение вида C(a,v), где C -число, (a,v) ~ I, назовем индукторным элементом(и- элементом) И- алгебры; cen(C(a,v)) = a , ind(C(a,v)) = v .

10.2. Восстановление индукции по алгебре.

Определение. Пусть A = Ialg(T,I). Левым клубом элемента x О A типа r(набор значений ранга) назовем множество ML[r](x) = { y | y О A; rnk(x*y) О r }. Правый клуб определим аналогично: MR[r](x) = { y | y О A; rnk(y*x) О r }. Элемент x лево- экстремален (право- экстремален, би- экстремален) по типу r, если для всех y О A соответственно ML[r](x+y) Н ML[r](x) ( MR[r](x+y) Н MR[r](x), оба свойства вместе ).

Лемма. И- алгебре любого И- пространства левоэкстремальны одновременно по .[0] и .[1] все и только индукторные элементы . Доказательство. Пусть x = x(1) + ... + x(N), где x(i) - и- элемент: x(i) = C(i)( a(i), v(i) ) . Тогда, либо все v(i) = v , либо найдутся два i,j, для которых D = (v(i) \v(j)) № Ж. Пусть b О D. Для любого и- элемента y = (b,w)  rnk(x*y) = 2 . Пусть z = Sx(j) | b П ind(x(j)); Тогда ML[1](x-z) Й ML[1](x) ; Значит x не лево- экстремален по [1]. Следовательно, .[1]- левоэкстремальность требует ind(x(i)) = v "i. Если не все a(i) = a, то положим z = Sx(j) | a № cen(x(j)); Тогда ML[0](x-z) Й ML[0](x) ; Значит x не лево-экстремален по [0]. Следовательно, .[0]- лево- экстремальность требует cen(x(i)) = a "i. Если x = C(a,v), то при y = c(a,v)  x+y = (C+c)(a,v);  ML[0](x+y) = ML[0](x); ML[1](x+y) = ML[1](x) ; при наличии в y слагаемого z: (cen(z), ind(z)) № (a,b) , как показано выше, либо ML[0](x+y) М ML[0](x) либо ML[1](x+y) М ML[1](x); Значит индукторные элементы .[0,1] -лево-экстремальны. ^[¯]

Следствие. При любом изоморфизме И- алгебр на любом пространстве индукторные элементы могут отображаться только в индукторные. Это трбование назовем условием мональности.

Теорема.И- алгебра определяет исходное И- пространство с точностью до изоморфизма. Доказательство. Определим точку t, как класс элементов алгебры, у которых совпадают MR[0](x) и MR[1](x) , причем MR[0](x) не пуст. Множество точек обозначим T. Прединдуктор точки t, это класс элементов алгебры с одинаковыми ML[0](x) и ML[1] , пересеченный с элементами алгебры из t. Соответствующий индуктор - множество точек, у которых прединдуктор входит в MR[0,1]. Легко видеть, что точка объединяет индукторные элементы алгебры с одним центром. А прединдуктор выделяет единственный индукторный элемент x с тем же центром. Построенный индуктор объединяет все точки, центры которых лежат в ind(x). Таким образом построен изоморфизм нового и исходного пространства.^[¯]

10.3. Теорема.Если две И-алгебры изоморфны, то их параметры умножения пропорциональны: L₁/ L₂ = Lў₁/ Lў₂ . Доказательство. Пусть f -изоморфизм И- алгебры с параметром умножения L1,L2 в И- алгебру с параметром умножения L1ў,L2ў . По условию мональности (следствие леммы 10.2) f(a,v) = C_a (aў,vў);  f(b,w) = C_b (bў,wў) , где C_a, C_b - числа. По свойству изоморфизма f( (a,v)*(b,w) ) = f(a,v)*f(b,w) = L₁ f(a,v) + L₂ f(b,w) = L₁ C_a (a,v) + L₂ C_b (b,w) = C_a(aў,vў) *C_b(bў,wў) = C_a C_b (a,v)* (b,w) = C_a C_b L1ў(aў,vў) + C_a C_b L2ў(bў,wў) . Тогда L₁ C_a = C_a C_b Lў₁; L₂ C_b = C_a C_b Lў₂ . Поскольку числа образуют поле, можно записать: C_a = L₂ / Lў₂; C_b = L₁ / Lў₁ . Повторив выкладку для f( (b,w)*(a,v) ) получим C_b = L₂ / Lў₂; C_a = L₁ / Lў₁ . ^[¯] Замечание. В приведенном доказательстве не учитывались ранги, которые неявно учтены в условии мональности.

10.4. Индукторные алгебры нечетких пространств.

Смеси И- пространств mix(c₁.I₁, ..., c_n.I_n) с числовыми весами сопоставим алгебру на векторах (x(1),...,x(n)), где x(i) принадлежит И- алгебре пространства (T,I_i), множество точек считаем общим для всех индукций. Параметры умножения в каждой алгебре определяются, как функция веса соответствующей индукции. Операции "+" и "*" определяются покоординатно. Такую алгебру назовем И- алгеброй смеси с заданной функцией параметров умножения.

Теорема. Если функция параметров умножения дает непропорциональное изменение первого и второго параметра по весу индукции в смеси, то неизоморфным смесям соответствуют неизоморфные И- алгебры. Это непосредственное следствие теоремы 10.3 . Подходящей функцией параметров умножения является , например, L₁ = c ;  L₂ = c² .

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

Литература

[1]

А. В. Коганов. Индукторные пространства и процессы. ДАН, том 324, ном. 5, 1992г., с 953-958.

[2]

A. V. Koganov. Processes and Automorphisms on Inductor Spaces. Russian Jornal of Mathematic Phusyk, vol 4, nom 3, 1996, s 315- 339.

[3]

А. В. Коганов.Представления групп автоморфизмами индукторных пространств. Тез. конф. "Алгебра и Анализ", КГУ, Казань, 1994г., с 50-51.

[4]

Р. Г. Нигматуллин, Нижние оценки сложности и сложность универсальных схем. Изд. КГУ, Казань, 1990г., 110 с.

[5]

А. В. Коганов.Алгоритмизация АСУ многопозиционными загрузочными устройствами. "Сталь", N 3, Металлургия, М., 1989.

[6]

Е. Е. Демидов. О некоторых аспектах теории квантовых групп. УМН, 1993г., т. 48 ном. 6, с 39-74. (Обзорная статья)

[7]

Е. Е. Демидов. Многообразие флагов и представления квантовой полной линейной группы. УМН, 1992г., т. 47, ном. 5, с 175-176.

[8]

Е. Е. Демидов. О многопараметрических квантовых деформациях группы GL[n]. УМН, 1991г., т. 46 ном. 4, с 147-148.