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

Чтобы узнать о других значениях, см. Зависимость (значения) .

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

В информатике , в частности в теории параллелизма , отношение зависимости — это бинарное отношение в конечной области. $\Sigma$, симметричный и рефлексивный ; т.е. конечное отношение допуска . То есть это конечное множество упорядоченных пар $D$, такой, что

• Если $(a,b)\in D$ затем $(b,a)\in D$ (симметричный)
• Если $a\in \Sigma$, затем $(a,a)\in D$ (рефлексивный)

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

$\Sigma$ также называется алфавитом, на котором $D$ определяется. Независимость , вызванная $D$ это бинарное отношение $I$

$I=(\Sigma \times \Sigma )\setminus D$

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

$D=(\Sigma \times \Sigma )\setminus I$

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

Пара $(\Sigma ,D)$ называется параллельным алфавитом . Пара $(\Sigma ,I)$ называется алфавитом независимости или алфавитом доверия , но этот термин может также относиться к тройному алфавиту. $(\Sigma ,D,I)$ (с $I$ вызванный $D$). Элементы $x,y\in \Sigma$ называются зависимыми, если $xDy$ выполняется и независимо , иначе (т.е. если $xIy$ держится).

Учитывая алфавит доверия $(\Sigma ,D,I)$, симметричное и иррефлексивное отношение $\doteq$ можно определить на свободном моноиде $\Sigma ^{*}$ всех возможных строк конечной длины следующим образом: $xaby\doteq xbay$ для всех строк $x,y\in \Sigma ^{*}$ и все независимые символы $a,b\in I$. эквивалентности Замыкание ​ $\doteq$ обозначается $\equiv$ или $\equiv _{(\Sigma ,D,I)}$ и позвонил $(\Sigma ,D,I)$-эквивалентность. Неофициально, $p\equiv q$ выполняется, если строка $p$ может быть преобразован в $q$ конечной последовательностью перестановок соседних независимых символов. Классы эквивалентности ​ $\equiv$ называются следами , и изучаются в теории следов .

Примеры

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

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