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

• (symmetric)

• (reflexive)

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

is also called the alphabet is defined. The independency

on a finite alphabet, the relation

is a dependency relation.

is called the concurrent alphabet. is called the independency alphabet or reliance alphabet). are called dependent holds, and independent holds).

can be defined on the free monoid. The equivalence closure by a finite sequence of swaps of adjacent independent symbols. The equivalence classes are called traces, and are studied in trace theory.

Examples

, see picture.

, but to no other string.

References