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

• If [math]\displaystyle{ (a,b)\in D }[/math] then [math]\displaystyle{ (b,a) \in D }[/math] (symmetric)
• If [math]\displaystyle{ a \in \Sigma }[/math], then [math]\displaystyle{ (a,a) \in D }[/math] (reflexive)

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

[math]\displaystyle{ \Sigma }[/math] is also called the alphabet on which [math]\displaystyle{ D }[/math] is defined. The independency induced by [math]\displaystyle{ D }[/math] is the binary relation [math]\displaystyle{ I }[/math]

[math]\displaystyle{ I = (\Sigma \times \Sigma) \setminus D }[/math]

That is, the independency is the set of all ordered pairs that are not in [math]\displaystyle{ D }[/math]. The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation [math]\displaystyle{ I }[/math] on a finite alphabet, the relation

[math]\displaystyle{ D = (\Sigma \times \Sigma) \setminus I }[/math]

is a dependency relation.

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

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

Examples

200px|right Given the alphabet [math]\displaystyle{ \Sigma=\{a,b,c\} }[/math], a possible dependency relation is [math]\displaystyle{ D = \{ (a,b),\, (b,a),\, (a,c),\, (c,a),\, (a,a),\, (b,b),\, (c,c) \} }[/math], see picture.

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