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

Для использования в других целях см. Зависимость (значения).

Не путать с Отношение зависимости, который является обобщением концепции линейной зависимости между элементами векторного пространства.

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

• Если ${\displaystyle (a,b)\in D}$ тогда ${\displaystyle (b,a)\in D}$ (симметричный)
• Если ${\displaystyle a}$ является элементом множества, на котором определено отношение, то ${\displaystyle (a,a)\in 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 p\equiv q}$ выполняется, если строка ${\displaystyle p}$ может быть преобразован в ${\displaystyle q}$ конечной последовательностью перестановок соседних независимых символов. В классы эквивалентности из ${\displaystyle \equiv }$ называются следы,^[1]:7–8 и изучаются в теория следов.

Примеры

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

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

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

1. IJsbrand Ян Альберсберг и Гжегож Розенберг (март 1988 г.). «Теория следов». Теоретическая информатика. 60 (1): 1–82. Дои:10.1016/0304-3975(88)90051-5.