Разработка алгоритмов планирования

Пучок взаимовлияний подпоследовательностей и subseq2 последовательности seq - это некоторое множество взаимовлияний IS(, subseq2)ÍINT(seq), в котором любое взаимовлияние a⬍f⬍bÎIS таково, что aÎи bÎsubseq2, где , subseq2Ìseq и subseq2 = Æ.

Пучок взаимовлияний IS(, subseq2) подобен пучку взаимовлияний IS(subseq3, subseq4), если любая пара подобных взаимовлияний inteIS(subseqi,subseq2) и int'ÎIS(subseq3,subseq4) такова, что:

либо 1) int - согласие и intʹ - согласие;

либо 2) int - конфликт и - конфликт.

Подобие пучков взаимовлияний обозначим так: IS(, subseq2) = IS(subseq3,).

Замечание. Наиболее короткая подпоследовательность состоит из одного действия.

Выделим в seq некоторую подпоследовательность mseq, не включающую действия start и finish.

Некоторую подпоследовательность mseqÌseq будем называть собственной подпоследовательностью, если mseq не включает действий start и finish, то есть, и . Подпоследовательность действий lseqÌseq такую, что для любых действий aÎlseq и bÎ mseq верно, что a<b и lseqÇmseq=Æ, будем называть левой подпоследовательностью для mseq.

Подпоследовательность действий rseqÌseq такую, что для любых действий aÎmseq и bÎrseq верно, что a<b и mseqÇrseq=Æ, будем называть правой подпоследовательностью для mseq

Собственную подпоследовательность mseq будем называть бесполезной подпоследовательностью действий и обозначать mseq→↻, если IS(lseq, mseq) ≡ IS(mseq, rseq), где lseq - левая подпоследовательность действий для mseq, rseq - правая подпоследовательность действий для mseq.

Удаление бесполезной собственной подпоследовательности mseq из seq приводит к последовательности seq' такой, что для любого взаимовлияния int=a⬍f⬍bÎINT(seq):

либо, 1) имеет место либо обычное преобразование, либо НЕ-преобразование int в такое взаимовлияние int=𝜒ʹ⬍f⬍𝛿ʹÎINT(seq'), что:

либо 1.а) int и int' являются конфликтами;

либо 1.6) int и int' являются согласиями,

либо, 2) имеет место нуль-преобразование int.

Если в некоторой последовательности seq существуют подпоследовательности mseq' и mseq" такие, что:

а) mseq'Ìmseq", причём a=a", где a' - первое действие mseq', a" - первое действие mseq",

б) IS(lseq,,mseq,)=IS(lseq",mseq"), где lseq=lseq" - левая подпоследовательность для mseq' и mseq",

в) IS(mseq',rseq')≅IS(mseq", rseq"), где rseq' - правая подпоследовательность для mseq', rseq" - правая подпоследовательность для mseq",

тогда собственная подпоследовательность mseqcÌseq такая, что mseqÌmseq" и

mseqÌmseq', является бесполезной.

При пошаговом преобразовании некоторой исходной последовательности seqÎSEQ путём добавления действий, существует шаг L, на котором будет сформирована последовательность seq'ÎSEQ, содержащая бесполезную подпоследовательность mseqÎseq'.