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, [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
- Si luego (simétrico)
- Si es un elemento del conjunto en el que se define la relación, entonces (reflexivo)
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 en el quese define, entonces la independencia inducida por es la relación binaria
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
es una relación de dependencia.
El par se llama alfabeto concurrente . [2] : 6 La parejase llama alfabeto de independencia o alfabeto de dependencia , pero este término también puede referirse al triple (con Inducido por ). [3] : 6 elementosse llaman dependientes sitiene, e independiente , else (es decir, sisostiene). [1] : 6
Dado un alfabeto de confianza , una relación simétrica e irreflexiva se puede definir en el monoide libre de todas las cadenas posibles de longitud finita mediante: para todas las cuerdas y todos los símbolos independientes . El cierre de equivalencia de se denota o y llamó -equivalencia. Informalmente aguanta si la cuerda se puede transformar en mediante una secuencia finita de intercambios de símbolos independientes adyacentes. Las clases de equivalencia dese denominan trazas , [1] : 7-8 y se estudian en la teoría de trazas .
Ejemplos de
Dado el alfabeto , una posible relación de dependencia es , vea la imagen.
La independencia correspondiente es . Entonces, por ejemplo, los símbolos son independientes entre sí y, por ejemplo, son dependientes. La cuerda es equivalente a y para , pero a ninguna otra cuerda.
Referencias
- ↑ a b c d 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 .
- ^ Vasconcelos, Vasco Thudichum (1992). Semántica de seguimiento para objetos concurrentes (tesis de MsC). Universidad de Keio. CiteSeerX 10.1.1.47.7099 .
- ^ 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 .