Independency relation

In computer science, in particular in concurrency theory, a dependency relation is a binary relation on a finite domain $\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 \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. 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$). 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: $x a b y \doteq x b a y$ 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_$ 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

200px, right
Given the alphabet $\Sigma=\$, a possible dependency relation is $D = \$, see picture.

The corresponding independency is $I=\$. Then e.g. the symbols $b,c$ are independent of one another, and e.g. $a,b$ are dependent. The string $a c b b a$ is equivalent to $a b c b a$ and to $a b b c a$, but to no other string.

References

{{reflist

Properties of binary relations