Соответственно классу сцепленности C определим множество его "расщепите-лей"как следующую часть Dмножества:

Splitters(C) = P(C) - {(п1,п2) хотя бы одна из дуг п1,п2 линейна}.

Дуги расщепителя образуют гнездо в некоторой Rвставке или Sвставке. В последнем случае либо они образуют гнездо в одном из повторяемых циклов, либо левая дуга входит в левый из повторяемых циклов, а правая - в соответствующий правый. Иное противоречило бы "скобочной"интерпретации элемента D множества.

3.2.4.2. Оценка числа повторов расщепителей в некоторых схемах

Для элементарной схемы Т и пары (п1,п2) е P обозначим через v(Т,п1,п2) число гнезд в Т, которые имеют вид (п1,Т,п2).

Пусть для гнезд (п1, Т, п2) и (П1 ,Т,п2) справедливо равенство (п1,п2) = ,п2). Тогда назовем эти гнезда одноименными.

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

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

Лемма 24. Пусть C - класс сцепленности, (п1,п2) е Splitters(C) и вставка Т в P(C) является схемой. Тогда глубина скобочной системы, получаемой из Т удалением каждой пары дуг, отличной от (п1,п2), не превосходит двух.

Доказательство. В противном случае вставка Т не была бы схемой □

Пример 14. Dc})

-О -о

3 7 90 О 8

с D множеством

{(1, 2), (3,4), (5, 6), (7, 8), (9, 0)} совпадает со своей сильно связной компонентой C. Splitters(C) = P (C) = P .В предложениисхеме 71931251264028 дуги расщепителя (1,2) образуют три гнезда. Указанная леммой скобочная система есть 112122. Ее глубина равна двум.

При оценке числа одноименных гнезд в элементарной схеме важно следующее утверждение.

Лемма 25. Пусть Т - элементарная схема без Sвставок (таковы, в частности, линия и формант, не являющийся Sвставкой), Т1 и Т2 - ее одноименные гнезда. Тогда: 1) ни одно из гнезд не является участком другого; 2) для любого ней -трального маршрута Т3 маршруты Т1Т3Т2 и Т2Т3Т1 не являются участками схемы

Доказательство. Действительно, в первом случае схема содержала бы S-вставку, во втором собственный участок схемы (например, ТгТа) являлся бы R-вставкой □

Лемма 26. Пусть Т - элементарная схема без Sвставок, v = max{v(Т,ni,n2) п2) G P}, p = parti(T), w = width(T), d = depth(T). Тогда

v <(1,d =1.

Доказательство. Представим T в виде Т = T1...Tp, где Ti имеет протяжение 1. Заметим, что скобочная система протяжения 1 может быть представлена ориенти -рованным деревом, корень которого отвечает паре внешних скобок. Из вершины, отвечаюшей некоторым парным скобкам, исходит столько дуг, каково протяжение заключенной в этих скобках подсистемы.

Следовательно, маршрут Ti, i = 1, ...,p, можно изобразить поддеревом wичного дерева высоты d, имеющего wd-i листьев.

Вследствие леммы 24 о взаимном расположении одноименных гнезд в элемен -тарной схеме величина v(Ti, п1, п2) оценивается числом wd-2 при d > 1 и единицей при d =1 для любой пары (п1,п2) G P. Действительно, среди конечных вершин дуг с общей начальной вершиной одна может отвечать паре (п1,п2), при условии что путь к ней от корня не содержит других вершин, отвечающих той же паре.

В случае d > 1 лемма следует из неравенства v(Т, п1,п2) < p • max{v(Ti,n1,n2) 1 < i < p}. В случае d =1 справедливо равенство v(Ti,n1,n2) = 1 в силу леммы о взаиморасположении одноименных гнезд □

Из леммы 26 и оценок ширины и глубины элементарной схемы следует, в частности, оценка

v(Т,7Г1,7Г2) < PP.

3.2.4.3. Секущие и их применение для классификации маршрутов, содержащих вершины итерантов. Ясно, что маршрут из вершины итеранта в вершину итеранта может быть сокращен удалением R вставок и повторяемых циклов до некоторой линии. Некоторые из линий, содержащих вершины итерантов, назо -вем секущими (см. определение ниже) и применим для описания маршрутов, не являющихся линиями.

Пусть маршрут Т = Т0Т1Т2 является линией, beg(T1) и end(T1) вершины ите -рантов некоторого класса C, Т0 и Т2 не содержат дуг итерантов того же класса. Тогда назовем Т1 секущей для класса C (в маршруте Т).

Отметим, что если Т является предложением и заряд (Т1) непуст, то образующие его дуги парны в данном предложении некоторым линейным дугам.

Заметим, что может быть несколько секущих с одинаковым зарядом и парой концов, и обозначим через Across(C, P, Q, w) множество всех секущих для класса C, которые имеют пару концов (P, Q) и заряд w.

Т G Across(C,P,Q,w), (п1,п2) G Splitters(C),

p = P(C) -{(П1,П2)},

pair(ni) = (Pi, Qi) для i = 1, 2.

Тогда в случае C > 1 обозначим через Code(T, ni, п2) объединение множеств Codei(T, П1,П2) = {(Ti,T2,Ta)Ti G Lines(p, P, Pi,wi), T2 G Lines(p, Qi, P2, Л), T3 G Lines(p, Q2, Q, w2); p(wiw2) = w}

Code2 (T, ni, П2) = {(Ti, T2, T3, T4, T5) Ti G Lines(p, P, Pi, wi), T2 G Lines(p, Qi, Pi, W3), T3 G Lines(p, Qi, P2, Л), T4 G Lines(p, Q2, P2, W4), T5 G Lines(p,Q2,Q,W2); p(wiW2) = w, 11(4)311)4) = Л}. Пусть C - класс сцепленности, C = 1. Пусть T G Across(C, P,Q,w), (п,п) G Splitters(C), p = P(C)-{(п,п)}, (пип2) G {(п,п), (Пpair(n) = (Pi,Qi) для i = 1, 2, m = max{v(TT - формант, beg(T) - вершина итеранта из C }. Тогда обозначим через Code(T,n,n) объединение 2m2 множеств Codek,i(T,ni,n2), 1 < k, l < m :

Codek,i(T, ni, П2) = {(Ti)i,Tit2k+i,T2,i,T2,2i+i

TM G Lines(p, P, Pi, wi,i);

Ti;j G Lines(p,Qi,P2,witj ),j = 2,2k;

Titj+i G Lines(p,Q2,Pi,witj+i),j = 2,2k при k> 1;

Ti,2fc+i G Lines(p,Q2,P,wi}2k+i);

T2)i G Lines(p, P, Pi,w2,i);

T2j G Lines(p,Qi,P2,w2,j),j = 2,2l;

T2,j+i G Lines(p,Q2,Pi,w2,j+i),j = 2,..., 2l при l > 1;

T2,2i+i G Lines(p,Q2,Q,w2,2i+i);

T = TitiniTit2n2...niTit2kn2Tit2k+i - Rвставка;

p(TT") = p(T") = w для T" = T2tiniT2,2n2...niT2t2in2T2,2i+i}.

Следующий пример показывает, что если ни одна из дуг расщепителя (п, п) не инцидентна какойлибо вершине секущей T, то маршрут TT может и не быть схемой. Однако "перемычки" Tj между ближайшими друг к другу вхождениями дуг расщепителя являются линиями (не обязательно нейтральными).

Пример 15. Эграф

с Эмножеством

P = {(1, 2), (3, 4)}

совпадает со своим единственным итерантом. Пустое предложение T является секущей. Указываемый элементом множества

Code(T, 3,4) = {(1, end(3), 2)}

маршрут (1, 3,4, 2) есть Rвставка, но не формант, так как содержит собственную R вставку (3, 4). 3.2.5. Специальные разложения маршрутов

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