Dependency relation

In computer science, in particular in concurrency theory, a dependency relation is a binary relation that is finite,[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

  • If then (symmetric)
  • If is an element of the set on which the relation is defined, then (reflexive)

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

If denotes the alphabet on which is defined, then 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.[2]:6 The pair is called the independency alphabet or reliance alphabet, but this term may also refer to the triple (with induced by ).[3]:6 Elements are called dependent if holds, and independent, else (i.e. if holds).[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: for all strings and all independent symbols . The equivalence closure of is denoted or and called -equivalence. Informally, holds if the string can be transformed into 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  , see picture.

The corresponding independency is  . Then e.g. the symbols   are independent of one another, and e.g.   are dependent. The string   is equivalent to   and to  , but to no other string.


  1. ^ a b c d IJsbrand Jan Aalbersberg and Grzegorz Rozenberg (Mar 1988). "Theory of traces". Theoretical Computer Science. 60 (1): 1–82. doi:10.1016/0304-3975(88)90051-5.
  2. ^ Vasconcelos, Vasco Thudichum (1992). Trace semantics for concurrent objects (MsC thesis). Keio University. CiteSeerX
  3. ^ Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). The Book of Traces. Singapore: World Scientific. ISBN 981-02-2058-8. Retrieved 18 April 2021.