Dependency relation

In computer science, in particular in concurrency theory, a dependency relation is a symmetric and reflexive: 6  binary relation on a finite domain Σ;: 4  i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs D, such that

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

Σ is also called the alphabet on which D is defined. The independency induced by D is the binary relation I

I=(Σ×Σ)∖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=(Σ×Σ)∖I

is a dependency relation.

The pair (Σ,D) is called the concurrent alphabet.: 6  The pair (Σ,I) is called the independency alphabet or reliance alphabet, but this term may also refer to the triple (Σ,D,I) (with I induced by D).: 6  Elements x,y∈Σ are called dependent if xDy holds, and independent, else (i.e. if xIy holds).: 6 

Given a reliance alphabet (Σ,D,I), a symmetric and irreflexive relation ≐ can be defined on the free monoid Σ∗ of all possible strings of finite length by: xaby≐xbay for all strings x,y∈Σ∗ and all independent symbols a,b∈I. The equivalence closure of ≐ is denoted ≡ or ≡(Σ,D,I) and called (Σ,D,I)-equivalence. Informally, p≡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 ≡ are called traces,: 7–8  and are studied in trace theory.

Examples

Given the alphabet Σ={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.