![]() | ||
In mathematics and computer science, a dependency relation is a binary relation that is finite, symmetric, and reflexive; i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs
In general, dependency relations are not transitive; thus, they generalize the notion of an equivalence relation by discarding transitivity.
Let
That is, the independency is the set of all ordered pairs that are not in
The pairs
The pairs of letters in an independency relation induce an equivalence relation on the free monoid of all possible strings of finite length. The elements of the equivalence classes induced by the independency are called traces, and are studied in trace theory.
Examples
Consider the alphabet
The corresponding independency is
Therefore, the letters