Dependency relation

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 $\mathrm{\Sigma }$, symmetric, and reflexive; i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs $D$, such that

• If $(a,b)\in D$ then $(b,a)\in D$ (symmetric)
• If $a\in \mathrm{\Sigma }$, then $(a,a)\in D$ (reflexive)

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

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

$I=(\mathrm{\Sigma }\times \mathrm{\Sigma })\setminus D$

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

$D=(\mathrm{\Sigma }\times \mathrm{\Sigma })\setminus I$

is a dependency relation.

The pair $(\mathrm{\Sigma },D)$ is called the concurrent alphabet. The pair $(\mathrm{\Sigma },I)$ is called the independency alphabet or reliance alphabet, but this term may also refer to the triple $(\mathrm{\Sigma },D,I)$ (with $I$ induced by $D$). Elements $x,y\in \mathrm{\Sigma }$ are called dependent if $xDy$ holds, and independent, else (i.e. if $xIy$ holds).

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

Examples

200px|right Given the alphabet $\mathrm{\Sigma }=\{a,b,c\}$, a possible dependency relation is $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)\}$. Then e.g. the symbols $b,c$ are independent of one another, and e.g. $a,b$ are dependent. The string $acbba$ is equivalent to $abcba$ and to $abbca$, but to no other string.