Порядок

Если s — копия начального отрезка t, то можно найти такое продолжение и последовательности s, что s^и = t. Определим отношение порядка

s t = ($u.s^и = t)

и будем говорить, что s является префиксом t. Например:<х, у> <х, у, z>. Отношение является частичным упорядочением и имеет своим наименьшим элементом <>. Об этом говорят законы

L1.<> s наименьший элемент.

L2.s s рефлексивность.

L3.s t AND t s t = sантисимметричность.

L4.s t AND t u s uтранзитивность.

Следующий закон вместе сL1 позволяет определить, является ли справедливым отношение s t:

L5.(<x>^s) t ºt <> AND x= t₀ AND s t’.

Будем говорить, что функция f из множества протоколов во множество протоколов монотонна, если она сохраняет отношение порядка , т. е. f(s) f(t) всякий раз, когда s t.

Длина

Длину протокола t будем обозначать #t. Например, #<х, у, z> = 3.

Следующие законы определяют операцию #:

L1.#<> = 0.

L2.#<x> = 1.

L3.#(s ^t) = #s + #t.

Число вхождений символа х в протокол s определяется как:

s ¯ х = #(s{х}).