Relación de dependencia

En informática , en particular en teoría de la concurrencia , una relación de dependencia es una relación binaria simétrica y reflexiva ^{[ 1 ] : 6} en un dominio finito ; ^{[ 1 ] : 4} es decir, una relación de tolerancia finita . Es decir, es un conjunto finito de pares ordenados , tal que${\displaystyle \Sigma }$${\displaystyle D}$

• Si entonces (simétrico)${\displaystyle (a,b)\in D}$${\displaystyle (b,a)\in D}$
• Si , entonces (reflexivo)${\displaystyle a\in \Sigma }$${\displaystyle (a,a)\in D}$

En general, las relaciones de dependencia no son transitivas ; por lo tanto, generalizan la noción de relación de equivalencia al descartar la transitividad.

${\displaystyle \Sigma }$También se le llama alfabeto sobre el cual se define. La independencia inducida por es la relación binaria.${\displaystyle D}$${\displaystyle D}$${\displaystyle I}$

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

Es decir, la independencia es el conjunto de todos los pares ordenados que no están en . La relación de independencia es simétrica e irreflexiva. Recíprocamente, dada cualquier relación simétrica e irreflexiva en un alfabeto finito, la relación${\displaystyle D}$${\displaystyle I}$

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

es una relación de dependencia.

El par se denomina alfabeto concurrente . ^{[ 2 ] : 6} El par se denomina alfabeto de independencia o alfabeto de dependencia , pero este término también puede referirse a la tripleta (con inducido por ). ^{[ 3 ] : 6} Los elementos se denominan dependientes si se cumple, e independientes en caso contrario (es decir, si se cumple). ^{[ 1 ] : 6}${\displaystyle (\Sigma ,D)}$${\displaystyle (\Sigma ,I)}$${\displaystyle (\Sigma ,D,I)}$${\displaystyle I}$${\displaystyle D}$${\displaystyle x,y\in \Sigma }$${\displaystyle xDy}$${\displaystyle xIy}$

Dado un alfabeto de dependencia , se puede definir una relación simétrica e irreflexiva en el monoide libre de todas las cadenas posibles de longitud finita mediante: para todas las cadenas y todos los símbolos independientes . El cierre de equivalencia de se denota o y se llama -equivalencia. De manera informal, se cumple si la cadena se puede transformar en mediante una secuencia finita de intercambios de símbolos independientes adyacentes. Las clases de equivalencia de se llaman trazas , ^{[ 1 ] : 7–8} y se estudian en la teoría de trazas .${\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 }$

Dado el alfabeto , una posible relación de dependencia es , ver imagen.${\displaystyle \Sigma =\{a,b,c\}}$${\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}}$

La independencia correspondiente es . Entonces, por ejemplo, los símbolos son independientes entre sí, y por ejemplo, son dependientes. La cadena es equivalente a y a , pero a ninguna otra cadena.${\displaystyle I=\{(b,c),\,(c,b)\}}$${\displaystyle b,c}$${\displaystyle a,b}$${\displaystyle acbba}$${\displaystyle abcba}$${\displaystyle abbca}$