Dependency relation

In computer science, in particular in concurrency theory, a dependency relation is a binary relation on a finite domain

,[1]: 4  symmetric, and reflexive;[1]: 6  i.e. a finite tolerance relation.

That is, it is a finite set of ordered pairs

, 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

The independency induced by

is the binary relation

That is, the independency is the set of all ordered pairs that are not in

The independency relation is symmetric and irreflexive.

Conversely, given any symmetric and irreflexive relation

on a finite alphabet, the relation is a dependency relation.

The pair

is called the concurrent alphabet.

is called the independency alphabet or reliance alphabet, but this term may also refer to the triple

induced by

are called dependent if

holds, and independent, else (i.e. if

[1]: 6 Given a reliance alphabet

, a symmetric and irreflexive relation

can be defined on the free monoid

of all possible strings of finite length by:

and all independent symbols

The equivalence closure of

holds if the string

by a finite sequence of swaps of adjacent independent symbols.

The equivalence classes of

are called traces,[1]: 7–8  and are studied in trace theory.

Given the alphabet

, a possible dependency relation is