Independency relation

☆ Save On Wikipedia ↗

In computer science, in particular in concurrency theory, a dependency relation is a symmetric and reflexive[1]: 6  binary relation on a finite domain Σ {\displaystyle \Sigma } {\displaystyle \Sigma };[1]: 4  i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs D {\displaystyle D} {\displaystyle D}, such that

  • If ( a , b ) ∈ D {\displaystyle (a,b)\in D} {\displaystyle (a,b)\in D} then ( b , a ) ∈ D {\displaystyle (b,a)\in D} {\displaystyle (b,a)\in D} (symmetric)
  • If a ∈ Σ {\displaystyle a\in \Sigma } {\displaystyle a\in \Sigma }, then ( a , a ) ∈ D {\displaystyle (a,a)\in D} {\displaystyle (a,a)\in D} (reflexive)

In general, dependency relations are not transitive; thus, they generalize the notion of an equivalence relation by discarding transitivity.

Σ {\displaystyle \Sigma } {\displaystyle \Sigma } is also called the alphabet on which D {\displaystyle D} {\displaystyle D} is defined. The independency induced by D {\displaystyle D} {\displaystyle D} is the binary relation I {\displaystyle I} {\displaystyle I}

I = ( Σ × Σ ) ∖ D {\displaystyle I=(\Sigma \times \Sigma )\setminus D} {\displaystyle I=(\Sigma \times \Sigma )\setminus D}

That is, the independency is the set of all ordered pairs that are not in D {\displaystyle D} {\displaystyle D}. The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation I {\displaystyle I} {\displaystyle I} on a finite alphabet, the relation

D = ( Σ × Σ ) ∖ I {\displaystyle D=(\Sigma \times \Sigma )\setminus I} {\displaystyle D=(\Sigma \times \Sigma )\setminus I}

is a dependency relation.

The pair ( Σ , D ) {\displaystyle (\Sigma ,D)} {\displaystyle (\Sigma ,D)} is called the concurrent alphabet.[2]: 6  The pair ( Σ , I ) {\displaystyle (\Sigma ,I)} {\displaystyle (\Sigma ,I)} is called the independency alphabet or reliance alphabet, but this term may also refer to the triple ( Σ , D , I ) {\displaystyle (\Sigma ,D,I)} {\displaystyle (\Sigma ,D,I)} (with I {\displaystyle I} {\displaystyle I} induced by D {\displaystyle D} {\displaystyle D}).[3]: 6  Elements x , y ∈ Σ {\displaystyle x,y\in \Sigma } {\displaystyle x,y\in \Sigma } are called dependent if x D y {\displaystyle xDy} {\displaystyle xDy} holds, and independent, else (i.e. if x I y {\displaystyle xIy} {\displaystyle xIy} holds).[1]: 6 

Given a reliance alphabet ( Σ , D , I ) {\displaystyle (\Sigma ,D,I)} {\displaystyle (\Sigma ,D,I)}, a symmetric and irreflexive relation ≐ {\displaystyle \doteq } {\displaystyle \doteq } can be defined on the free monoid Σ ∗ {\displaystyle \Sigma ^{*}} {\displaystyle \Sigma ^{*}} of all possible strings of finite length by: x a b y ≐ x b a y {\displaystyle xaby\doteq xbay} {\displaystyle xaby\doteq xbay} for all strings x , y ∈ Σ ∗ {\displaystyle x,y\in \Sigma ^{*}} {\displaystyle x,y\in \Sigma ^{*}} and all independent symbols a , b ∈ I {\displaystyle a,b\in I} {\displaystyle a,b\in I}. The equivalence closure of ≐ {\displaystyle \doteq } {\displaystyle \doteq } is denoted ≡ {\displaystyle \equiv } {\displaystyle \equiv } or ≡ ( Σ , D , I ) {\displaystyle \equiv _{(\Sigma ,D,I)}} {\displaystyle \equiv _{(\Sigma ,D,I)}} and called ( Σ , D , I ) {\displaystyle (\Sigma ,D,I)} {\displaystyle (\Sigma ,D,I)}-equivalence. Informally, p ≡ q {\displaystyle p\equiv q} {\displaystyle p\equiv q} holds if the string p {\displaystyle p} {\displaystyle p} can be transformed into q {\displaystyle q} {\displaystyle q} by a finite sequence of swaps of adjacent independent symbols. The equivalence classes of ≡ {\displaystyle \equiv } {\displaystyle \equiv } are called traces,[1]: 7–8  and are studied in trace theory.

Examples

Given the alphabet Σ = { a , b , c } {\displaystyle \Sigma =\{a,b,c\}} {\displaystyle \Sigma =\{a,b,c\}}, a possible dependency relation is D = { ( a , b ) , ( b , a ) , ( a , c ) , ( c , a ) , ( a , a ) , ( b , b ) , ( c , c ) } {\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}} {\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}}, see picture.

The corresponding independency is I = { ( b , c ) , ( c , b ) } {\displaystyle I=\{(b,c),\,(c,b)\}} {\displaystyle I=\{(b,c),\,(c,b)\}}. Then e.g. the symbols b , c {\displaystyle b,c} {\displaystyle b,c} are independent of one another, and e.g. a , b {\displaystyle a,b} {\displaystyle a,b} are dependent. The string a c b b a {\displaystyle acbba} {\displaystyle acbba} is equivalent to a b c b a {\displaystyle abcba} {\displaystyle abcba} and to a b b c a {\displaystyle abbca} {\displaystyle abbca}, but to no other string.

References

  1. IJsbrand Jan Aalbersberg and Grzegorz Rozenberg (Mar 1988). "Theory of traces". Theoretical Computer Science. 60 (1): 1–82. doi:10.1016/0304-3975(88)90051-5.
  2. Vasconcelos, Vasco Thudichum (1992). Trace semantics for concurrent objects (MsC thesis). Keio University.
  3. Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). The Book of Traces. Singapore: World Scientific. ISBN 981-02-2058-8. Retrieved 18 April 2021.