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 en un dominio finito , ^{[1] : 4} simétrica y reflexiva ; ^{[1] : 6,} 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 tanto, generalizan la noción de relación de equivalencia al descartar la transitividad.

${\displaystyle \Sigma }$También se llama alfabeto al que 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. 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 . ^{[2] : 6} El par se llama alfabeto de independencia o alfabeto de dependencia , pero este término también puede referirse al triple (con inducido por ). ^{[3] : 6} elementos se llaman dependientes si se cumple, e independientes , en caso contrario (es decir, si se cumple). ^{[  dieciséis} ${\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 puede transformarse mediante una secuencia finita de intercambios de símbolos independientes adyacentes. Las clases de equivalencia de se denominan 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 }$

Ejemplos

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}$

Referencias

1. IJsbrand Jan Aalbersberg y Grzegorz Rozenberg (marzo de 1988). "Teoría de las huellas". Informática Teórica . 60 (1): 1–82. doi : 10.1016/0304-3975(88)90051-5 .
2. Vasconcelos, Vasco Thudichum (1992). Semántica de seguimiento para objetos concurrentes (tesis de maestría). Universidad de Keio. CiteSeerX 10.1.1.47.7099 . 
3. Mazurkiewicz, Antoni (1995). "Introducción a la teoría de la traza" (PDF) . En Rozenberg, G.; Diekert, V. (eds.). El Libro de las Huellas . Singapur: World Scientific. ISBN 981-02-2058-8. Consultado el 18 de abril de 2021 .