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

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

• Если то (симметрично)${\displaystyle (a,b)\in D}$${\displaystyle (б,а)\в D}$
• Если , то (рефлексивно)${\displaystyle a\in \Сигма}$${\displaystyle (а,а)\in D}$

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

${\displaystyle \Сигма}$также называется алфавитом , на котором определяется. Независимость , вызванная бинарным отношением${\displaystyle D}$${\displaystyle D}$${\displaystyle Я}$

${\displaystyle I=(\Sigma \times \Sigma )\setminus D}$

То есть независимость — это множество всех упорядоченных пар, которые не находятся в . Отношение независимости симметрично и иррефлексивно. Наоборот, если задано любое симметричное и иррефлексивное отношение на конечном алфавите, отношение${\displaystyle D}$${\displaystyle Я}$

${\displaystyle D=(\Sigma \times \Sigma )\setminus I}$

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

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

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

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

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