Алгебра кортежей. Голова, префикс, подпоследовательность кортежа.

1. – мощность

2. «+», «^», «.» – конкатенация.

s . t – конкатенация двух кортежей

Для любого кортежа s справедливо: < > . s = s . < > = s

3. – сужение кортежа по . – алфавит (множество)

– в t остаются только те элементы, которые есть в А; определяется новый домен для кортежа .

[ ] относительно операции сужения пустой кортеж есть 0. Хмм…

(s . t) – дистрибутивность операции сужения относительно конкатенации

если

если

4. Голова кортежа – его первый элемент. Обозн.: s_o = <x, y, z>_o = x.

Хвост – оставшаяся после удаления головы часть кортежа. Обозн.: s’ = <x, y, z>’ = <y, z>

Пример: t = < t_o . t’ > для "t ¹ < >.

5. Префикс связан с отношением порядка над кортежами.

Пусть s – некоторый кортеж, равный начальному отрезку кортежа t;

s £ t º $ u: [ s . u = t ]

s называется префиксом t т. и т. т., когда $ u, такой, что конкатенация s . u даёт t.

Если s £ t, то они связаны отношением включения.

Свойства этого отношения:

1) < > £ s для "s

2) s £ s (рефлексивность)

3) s £ t & t £ s => s = t (антисимметричность)

(<x> . s) £ t º (t ¹ < >) & (x = t_o) & (s £ t’)

"u "s "t [ s £ u & t £ u => s £ t Ú t £ s ]