считая, что

0G Names(Z).

Начальная буква A в данном и в двух следующих обозначениях взята от слова Augmentation.

ANames(() = Names(() U {0}, AAlph(() = Alph(() U{(o, )o}. Нижеследующее вспомогательное обозначение использует понятие "пополнен-ных"фракций как основу:

Alternatives(i) = {£\3(x,y,z G AAlph(()*) [x(1y)1z G ATrim(Z); С G reduction(y)}}

1G ANames(().

Сформируем укорочение

Squeeze(Z)

КСвыражения ( как сумму, возможно, вырожденную - из одного слагаемого. Может случиться, что слагаемое КСвыражения Squeeze(Z) не будет удовлетворять определению фракции, т.е. в нем к невырожденным суммам будет приме няться операция умножения или именования.

Приближения искомого КСвыражения будут представлены цепочкой

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

Building,

очередных добавляемых к рассмотрению -

Storey.

Ясно, что при первоначально пустом множестве Building добавлений к нему будет не больше числа \ANames(()\.

Гнезда в формируемых слагаемых будут до поры до времени изображаться цепочками вида

i G ANames(Z).

(Такую цепочку будем называть i - заглушкой, или, собирательно, заглушкой. В связи с этим для описания "полуфабриката"КС выражения Squeeze( ) полезна функция, отображающая фракцию в цепочку заглушек и символов языка; для произвольной фракции С над алфавитом Е эта функция определяется следующим образом:

Г С, С G Е U {е}, ground(C) = < d)i, С = (iu)i для i G ANames(Z), u G Alph(()*, [ ground()ground), С = С1С2 для фракций С1,С2•

Устранение заглушек будет осуществляться с помощью описываемой далее процедуры

Replacement (с).

Устранение происходит поэтапно, при все более подробной их "расшифровке", раскрытии. Раскрывающий материал предоставляется на последнем этапе - множеством Alternatives (с), вернее, самыми короткими его элементами, на промежуточных этапах - величиной

Embedding s (с). Ее значением является множество

{u3[v G ANames(Z) - Building - Storey, x,y,z G Alph(()*]

[£ = x(vy)vz G Alternatives(t), u = ground(£)]}

цепочек, вовлекающих еще не использовавшиеся в Sqz имена. Эти имена составляют множество

New(C) = {v G Building U Storey\z\[x, y G Alph(()*]

x(v)vy G Embeddings(с)}.

Алгоритм 3. Укорачивание КСвыражения. Вход. КСвыражение

являющееся суммой приведенных фракций. Выход. КСвыражение

Squeeze(Z), определяемое конструкцией алгоритма.

Шаг 1. Sqz := (0)0;

Building := 0; Storey := {0}.

Шаг 2. Пока Storey = 0, выполнять следующие действия 2.1-2.2.

2.1.Для каждого имени с G Storey вычислить множества New (с) и Embeddings(i) и выполнить процедуру Replacement(с).

2.2.Building := Building U Storey; Вычислить объединение

Ui&storeyNew (с) и сделать его новым значением величины Storey.

Шаг 3. Для каждого имени с G Names(() заменить каждую сзаглушку, еще присутствующую в цепочке Sqz, гнездом (t£)t, где £ G Alternatives (с) есть какая -либо из альтернатив, имеющих минимальную длину.

Шаг 4. Стереть "искусственные"скобки (0, )0. Положить результирующее КС -выражение равным значению величины Sqz.

Процедура Replacement внедряет в цепочку Sqz вместо заглушек с заданным именем (возможно, не всех) некоторые их расшифровки. Не раскрытые заглушки обрабатываются шагом 3 алгоритма 3. Для этого используются кратчайшие из альтернатив, определяющих одноименные гнезда КСвыражения (.

Число раскрываемых процедурой заглушек есть минимальное из числа их вхождений в Sqz и \Embeddings(i)\. Если последние два числа равны, то каждому вхождению заглушки отвечает один элемент из Embeddings(i). При избытке материала, подлежащего внедрению, какойлибо один экземпляр заглушки заменяется именованной суммой (например, при наличии нескольких фракций в ATrim(() внутрь исходной 0заглушки попадет сумма). Таким образом, используется весь этот материал. При нехватке материала обработка "лишних"заглушек откладывается, чтобы не увеличивать длину цепочки Sqz.

Алгоритм 4. Replacement

Вход. Имя i Е ANames(Z); текущее значение величины Sqz. Выход. Преобразованное значение Sqz.

Вспомогательные обозначения. Число mt вхождений бзаглушки в Sqz;

m = min(\Embeddings(i)\, mt);

Individuals С Embeddings(i), Group С Embeddings(i) есть одна любая из пар множеств, удовлетворяющих соотношениям

\Individuals\ = m - 1,

Group = Embeddings(i) - Individuals.

Шаг 1. Выбрать какиелибо m - 1 вхождений в Sqz бзаглушки, например, первые при переборе вхождений слева направо. Определить одну из возможных биекций выбранного множества на множество Individuals. Каждое из выбранных вхождений заменить .гнездом

u Е Individuals

есть образ данного вхождения бзаглушки.

Шаг 2. Одно из незаменявшихся вхождений бзаглушки в Sqz (таких может быть больше одного при \Embeddings(i)\ < mt) заменить .гнездом, заключающим сумму элементов множества Group:

udGroup

Пусть i - некоторое имя, С - бгнездо. Определим рекурсивно понятие среза гнезда С и числовую характеристику среза, называемую его статусом:

1)заглушка (t)t является срезом гнезда С, имеющим нулевой статус;

С = (iu)i

и для некоторого l > 0

u = voCivi. Civi,

где цепочка vj, 0 < j < l, не содержит именованных скобок, а С», 1 < i < l, есть гнездо, имеющее срез щ со статусом s», то цепочка

(tvouivi uivi)i