Отношение зависимости - Dependency relation

В Информатика, в частности в теория параллелизма, а отношение зависимости это бинарное отношение что конечно,^[1]^:4 симметричный, и рефлексивный;^[1]^:6 т.е. конечный отношение терпимости. То есть это конечный набор заказанные пары ${ displaystyle D}$ , так что

Если ${ displaystyle (a, b) in D}$ тогда ${ displaystyle (b, a) in D}$ (симметричный)
Если ${ displaystyle a}$ является элементом множества, на котором определено отношение, то ${ Displaystyle (а, а) в D}$ (возвратный)

В общем, отношения зависимости не переходный; таким образом, они обобщают понятие отношение эквивалентности отбрасывая транзитивность.

Если ${ displaystyle Sigma}$ (также называемый алфавит ) обозначает множество, на котором ${ displaystyle D}$ определено, то независимость индуцированный ${ displaystyle D}$ это бинарное отношение ${ displaystyle I}$

{ Displaystyle I = ( Sigma times Sigma) setminus D}

То есть независимость - это набор всех упорядоченных пар, не входящих в ${ displaystyle D}$ . Отношение независимости симметрично и иррефлексивно. И наоборот, для любого симметричного и иррефлексивного отношения ${ displaystyle I}$ на конечном алфавите соотношение

{ Displaystyle D = ( Sigma times Sigma) setminus I}

это отношение зависимости.

Пары ${ Displaystyle ( Sigma, D)}$ и ${ Displaystyle ( Sigma, I)}$ ,^{[нужна цитата ]} или тройка ${ Displaystyle ( Sigma, D, I)}$ (с ${ displaystyle I}$ индуцированный ${ displaystyle D}$ ) иногда называют параллельный алфавит^{[нужна цитата ]} или алфавит доверия. В этом случае элементы ${ displaystyle x, y in Sigma}$ называются зависимый если ${ displaystyle xDy}$ держит, и независимый, иначе (т.е. если ${ displaystyle xIy}$ держит).^[1]^:6

Учитывая алфавит доверия ${ Displaystyle ( Sigma, D, I)}$ , симметричное и иррефлексивное отношение ${ displaystyle doteq}$ можно определить на свободный моноид ${ Displaystyle Sigma ^ {*}}$ всех возможных строк конечной длины на: ${ displaystyle xaby doteq xbay}$ для всех струн ${ displaystyle x, y in Sigma ^ {*}}$ и все независимые символы ${ displaystyle a, b in I}$ . В закрытие эквивалентности из ${ displaystyle doteq}$ обозначается ${ Displaystyle Equiv}$ , или же ${ Displaystyle Equiv _ {( Sigma, D, I)}}$ , и назвал ${ Displaystyle ( Sigma, D, I)}$ -эквивалентность. Неофициально ${ Displaystyle р экв q}$ выполняется, если строка ${ displaystyle p}$ может быть преобразован в ${ displaystyle q}$ конечной последовательностью перестановок соседних независимых символов. В классы эквивалентности из ${ Displaystyle Equiv}$ называются следы,^[1]^:7–8 и изучаются в теория следов.

Примеры

Учитывая алфавит ${ Displaystyle Sigma = {а, б, с }}$ , возможное отношение зависимости ${ Displaystyle D = {(a, b), , (b, a), , (a, c), , (c, a), , (a, a), , (b, б), , (в, в) }}$ см. картинку.

Соответствующая независимость ${ Displaystyle I = {(Ь, с), , (с, Ь) }}$ . Тогда, например, символы ${ displaystyle b, c}$ независимы друг от друга, и, например, ${ displaystyle a, b}$ зависимы. Струна ${ displaystyle acbba}$ эквивалентно ${ displaystyle abcba}$ и чтобы ${ displaystyle abbca}$ , но никакую другую строку.

Отношение зависимости - Dependency relation

Примеры

Рекомендации