In computer science, especially in concurrency theory, a dependency relation is a type of relationship that is symmetric and reflexive, involving a finite set called Σ. This means it consists of a finite collection of ordered pairs, D, which follow certain rules.

Usually, these relations are not transitive. This makes them a broader version of equivalence relations, which do require transitivity.

Σ is also called the alphabet on which D is defined. The independency induced by D is the binary relation I. This relationship includes all pairs not found in D. The independency relation is symmetric and does not include any element paired with itself.

If there is a symmetric and irreflexive relationship I on a finite alphabet, then a dependency relation D can be formed from it.

The pair (Σ, D) is called the concurrent alphabet. The pair (Σ, I) is sometimes called the independency or reliance alphabet. However, the term might also refer to the triple (Σ, D, I), where I is based on D. Elements x, y ∈ Σ are called dependent if xDy holds, and independent if xIy holds.

Using the reliance alphabet (Σ, D, I), a symmetric and irreflexive relationship ≐ can be created on the set of all possible strings made from Σ. For example, if two independent symbols a and b appear next to each other in a string, they can be swapped. The equivalence closure of ≐ is called ≡ or ≡(Σ, D, I), and it represents strings that can be transformed into each other by swapping adjacent independent symbols. These groups of related strings are called traces and are studied in trace theory.

Examples

Using the alphabet Σ = {a, b, c}, one example of a dependency relation is D = {(a, b), (b, a), (a, c), (c, a), (a, a), (b, b), (c, c)}. This relation defines how symbols can be connected or related to each other. The corresponding independency relation is I = {(b, c), (c, b)}, which shows pairs of symbols that are not connected. For instance, b and c are independent, while a and b are dependent. The string "acbba" is considered equivalent to "abcba" and "abbca" under these rules, but it is not equivalent to any other string.