Dependency relation explained

In computer science, in particular in concurrency theory, a dependency relation is a binary relation on a finite domain

\Sigma ,^[1] symmetric, and reflexive;^[1] i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs D , such that

• If

(a,b)\in D then (b,a) \in D (symmetric)

• If

a \in \Sigma , then (a,a) \in D (reflexive)

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

\Sigma is also called the alphabet on which D is defined. The independency induced by D is the binary relation I I = (\Sigma x \Sigma) \setminus D

That is, the independency is the set of all ordered pairs that are not in

D . The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation I on a finite alphabet, the relationD = (\Sigma x \Sigma) \setminus I

is a dependency relation.

The pair

(\Sigma, D) is called the concurrent alphabet.^[2] The pair (\Sigma, I) is called the independency alphabet or reliance alphabet, but this term may also refer to the triple (\Sigma, D, I) (with I induced by D ).^[3] Elements x,y \in \Sigma are called dependent if xDy holds, and independent, else (i.e. if xIy holds).^[1]

Given a reliance alphabet

(\Sigma, D, I) , a symmetric and irreflexive relation • eq can be defined on the free monoid \Sigma ^{*} of all possible strings of finite length by: x a b y • eq x b a y for all strings x, y \in \Sigma ^{*} and all independent symbols a, b \in I . The equivalence closure of • eq is denoted \equiv or \equiv _{(\Sigma,} and called (\Sigma, D, I) -equivalence. Informally, p \equiv q holds if the string p can be transformed into q by a finite sequence of swaps of adjacent independent symbols. The equivalence classes of \equiv are called traces,^[1] and are studied in trace theory.

Examples

200px|rightGiven the alphabet

\Sigma = \{a,b,c\} , a possible dependency relation is D = \{ (a,b), (b,a), (a,c), (c,a), (a,a), (b,b), (c,c) \} , see picture.

The corresponding independency is

I = \{(b,c),(c,b)\} . Then e.g. the symbols b,c are independent of one another, and e.g. a,b are dependent. The string a c b b a is equivalent to a b c b a and to a b b c a , but to no other string.

Notes and References

1. 10.1016/0304-3975(88)90051-5 . IJsbrand Jan Aalbersberg and Grzegorz Rozenberg . Theory of traces . Theoretical Computer Science . 60 . 1 . 1 - 82 . Mar 1988 . free .
2. Vasconcelos . Vasco Thudichum . 1992 . Trace semantics for concurrent objects . MsC . Keio University. 10.1.1.47.7099.
3. Book: Mazurkiewicz . Antoni . Rozenberg . G. . Diekert . V. . The Book of Traces . 1995 . World Scientific . Singapore . 981-02-2058-8 . http://www.cas.mcmaster.ca/~cas724/2007/paper2.pdf . 18 April 2021 . Introduction to Trace Theory.