Dependency relation

In computer science, in particular in concurrency theory, 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 formula_1, such that
In general, dependency relations are not transitive; thus, they generalize the notion of an equivalence relation by discarding transitivity.
If formula_6 denotes the alphabet on which formula_1 is defined, then the independency induced by formula_1 is the binary relation formula_9
That is, the independency is the set of all ordered pairs that are not in formula_1. The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation formula_9 on a finite alphabet, the relation
is a dependency relation.
The pair formula_14 is called the concurrent alphabet. The pair formula_15 is called the independency alphabet or reliance alphabet, but this term may also refer to the triple formula_16 (with formula_9 induced by formula_1). Elements formula_19 are called dependent if formula_20 holds, and independent, else (i.e. if formula_21 holds).
Given a reliance alphabet formula_16, a symmetric and irreflexive relation formula_23 can be defined on the free monoid formula_24 of all possible strings of finite length by: formula_25 for all strings formula_26 and all independent symbols formula_27. The equivalence closure of formula_23 is denoted formula_29 or formula_30 and called formula_16-equivalence. Informally, formula_32 holds if the string formula_33 can be transformed into formula_34 by a finite sequence of swaps of adjacent independent symbols. The equivalence classes of formula_29 are called traces, and are studied in trace theory.
Examples.
Given the alphabet formula_36, a possible dependency relation is formula_37, see picture. 
The corresponding independency is formula_38. Then e.g. the symbols formula_39 are independent of one another, and e.g. formula_40 are dependent. The string formula_41 is equivalent to formula_42 and to formula_43, but to no other string.