Relación de dependencia - Dependency relation

En informática , en particular en la teoría de la concurrencia , una relación de dependencia es una relación binaria que es finita, simétrica y reflexiva ; es decir, una relación de tolerancia finita . Es decir, es un conjunto finito de pares ordenados , tal que ${\ Displaystyle D}$

• Si entonces (simétrico)${\ Displaystyle (a, b) \ in D}$${\ Displaystyle (b, a) \ in D}$
• Si es un elemento del conjunto en el que se define la relación, entonces (reflexivo)${\ Displaystyle a}$${\ Displaystyle (a, a) \ in D}$

En general, las relaciones de dependencia no son transitivas ; así, generalizan la noción de relación de equivalencia descartando la transitividad.

Si denota el alfabeto sobre el que se define, entonces la independencia inducida por es la relación binaria${\ Displaystyle \ Sigma}$${\ 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. Por el contrario, 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 llama alfabeto concurrente . El par se llama alfabeto de independencia o alfabeto de dependencia , pero este término también puede referirse al triple (con inducido por ). Los elementos se denominan dependientes si se cumplen e independientes , de lo contrario (es decir, si se cumplen ). ${\ 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 confianza , 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 mediante una secuencia finita de intercambios de símbolos independientes adyacentes. Las clases de equivalencia de se denominan trazas 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}$

Ejemplos de

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 al ya , pero a ninguna otra cadena. ${\ Displaystyle I = \ {(b, c), \, (c, b) \}}$${\ Displaystyle b, c}$${\ Displaystyle a, b}$${\ displaystyle acbba}$${\ displaystyle abcba}$${\ displaystyle abbca}$

Referencias