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

• If ( a , b ) ∈ D {\displaystyle (a,b)\in D} then ( b , a ) ∈ D {\displaystyle (b,a)\in D} (symmetric)
• If a ∈ Σ {\displaystyle a\in \Sigma } , then ( a , a ) ∈ D {\displaystyle (a,a)\in D} (reflexive)

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

Σ {\displaystyle \Sigma } is also called the alphabet on which D {\displaystyle D} is defined. The independency induced by D {\displaystyle D} is the binary relation I {\displaystyle I}

I = ( Σ × Σ ) ∖ D {\displaystyle I=(\Sigma \times \Sigma )\setminus D}

That is, the independency is the set of all ordered pairs that are not in D {\displaystyle D} . The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation I {\displaystyle I} on a finite alphabet, the relation

D = ( Σ × Σ ) ∖ I {\displaystyle D=(\Sigma \times \Sigma )\setminus I}

is a dependency relation.

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

Given a reliance alphabet ( Σ , D , I ) {\displaystyle (\Sigma ,D,I)} , a symmetric and irreflexive relation ≐ {\displaystyle \doteq } can be defined on the free monoid Σ ∗ {\displaystyle \Sigma ^{*}} of all possible strings of finite length by: x a b y ≐ x b a y {\displaystyle xaby\doteq xbay} for all strings x , y ∈ Σ ∗ {\displaystyle x,y\in \Sigma ^{*}} and all independent symbols a , b ∈ I {\displaystyle a,b\in I} . The equivalence closure of ≐ {\displaystyle \doteq } is denoted ≡ {\displaystyle \equiv } or ≡ ( Σ , D , I ) {\displaystyle \equiv _{(\Sigma ,D,I)}} and called ( Σ , D , I ) {\displaystyle (\Sigma ,D,I)} -equivalence. Informally, p ≡ q {\displaystyle p\equiv q} holds if the string p {\displaystyle p} can be transformed into q {\displaystyle q} by a finite sequence of swaps of adjacent independent symbols. The equivalence classes of ≡ {\displaystyle \equiv } are called traces,: 7–8  and are studied in trace theory.