Dependency relation

For other uses, see Dependency (disambiguation).

Not to be confused with Dependence relation, which is a generalization of the concept of linear dependence among members of a vector space.

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

* If  ( a , b ) ∈ D {\displaystyle (a,b)\in D} then  ( b , a ) ∈ D {\displaystyle (b,a)\in D} (symmetric)
* If  a ∈ Σ {\displaystyle a\in \Sigma } , then  ( a , a ) ∈ 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 } is also called the alphabet on which  D {\displaystyle D} is defined. The independency induced by  D {\displaystyle D} is the binary relation  I {\displaystyle I}

I = ( Σ × Σ ) ∖ 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} . The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation  I {\displaystyle I} on a finite alphabet, the relation

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

is a dependency relation.

The pair  ( Σ , D ) {\displaystyle (\Sigma ,D)} is called the concurrent alphabet.[2]: 6 The pair  ( Σ , 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)} (with  I {\displaystyle I} induced by  D {\displaystyle D} ).[3]: 6 Elements  x , y ∈ Σ {\displaystyle x,y\in \Sigma } are called dependent if  x D y {\displaystyle xDy} holds, and independent, else (i.e. if  x I y {\displaystyle xIy} holds).[1]: 6

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

## Examples

[edit]

Given the alphabet  Σ = { 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)\\}} , see picture.

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

## References

[edit]

1. ^ a b c d 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. CiteSeerX 10.1.1.47.7099.
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.