# Dependency relation

In computer science, in particular in concurrency theory, a dependency relation is a binary relation on a finite domain $\Sigma$ ,: 4  symmetric, and reflexive;: 6  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 \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.

$\Sigma$ is also called the alphabet on which $D$ is defined. 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 pair $(\Sigma ,D)$ is called the concurrent alphabet.: 6  The pair $(\Sigma ,I)$ is called the independency alphabet or reliance alphabet, but this term may also refer to the triple $(\Sigma ,D,I)$ (with $I$ induced by $D$ ).: 6  Elements $x,y\in \Sigma$ are called dependent if $xDy$ holds, and independent, else (i.e. if $xIy$ holds).: 6

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,: 7–8  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.