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 that is finite, 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$ is an element of the set on which the relation is defined, 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.

If $\Sigma$ (also called alphabet) denotes the set on which $D$ is defined, then the independency induced by $D$ is the binary relation $I$

$I=(\Sigma \times \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=(\Sigma \times \Sigma )\setminus I$

is a dependency relation.

The pairs $(\Sigma ,D)$ and $(\Sigma ,I)$, or the triple $(\Sigma ,D,I)$ (with $I$ induced by $D$) are sometimes called the concurrent alphabet or the reliance alphabet. In this case, elements $x,y\in \Sigma$ are called dependent if $xDy$ holds, and independent, else (i.e. if $xIy$ holds).

Given a reliance alphabet $(\Sigma ,D,I)$, a symmetric and irreflexive relation $\doteq$ can be defined on the free monoid $\Sigma ^{*}$ of all possible strings of finite length by: $xaby\doteq xbay$ for all strings $x,y\in \Sigma ^{*}$ and all independent symbols $a,b\in I$. The equivalence closure of $\doteq$ is denoted $\equiv$, or $\equiv _{(\Sigma ,D,I)}$, and called $(\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

Given the alphabet $\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.