Dependency relation

{{Short description|Binary relation in computer science}}

{{other uses|Dependency (disambiguation)}}

{{hatnote|Not to be confused with Dependence relation, which is a generalization of the concept of linear dependence among members of a vector space.}}

In computer science, in particular in concurrency theory, a dependency relation is a binary relation on a finite domain $\backslash Sigma$,{{cite journal | doi=10.1016/0304-3975(88)90051-5 | author=IJsbrand Jan Aalbersberg and Grzegorz Rozenberg | title=Theory of traces | journal=Theoretical Computer Science | volume=60 | number=1 | pages=1–82 | date=Mar 1988 | doi-access=free }}{{rp|4}} symmetric, and reflexive;{{rp|6}} i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs $D$, such that

• If $(a,b)\backslash in\; D$ then $(b,a)\; \backslash in\; D$ (symmetric)
• If $a\; \backslash in\; \backslash Sigma$, then $(a,a)\; \backslash in\; D$ (reflexive)

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

$\backslash Sigma$ is also called the alphabet on which $D$ is defined. The independency induced by $D$ is the binary relation $I$

:$I\; =\; (\backslash Sigma\; \backslash times\; \backslash Sigma)\; \backslash 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 relation

:$D\; =\; (\backslash Sigma\; \backslash times\; \backslash Sigma)\; \backslash setminus\; I$

is a dependency relation.

The pair $(\backslash Sigma,\; D)$ is called the concurrent alphabet.{{cite thesis |last=Vasconcelos |first=Vasco Thudichum |date=1992 |title=Trace semantics for concurrent objects |degree=MsC |publisher=Keio University|citeseerx=10.1.1.47.7099}}{{rp|6}} The pair $(\backslash Sigma,\; I)$ is called the independency alphabet or reliance alphabet, but this term may also refer to the triple $(\backslash Sigma,\; D,\; I)$ (with $I$ induced by $D$).{{cite book |last1=Mazurkiewicz |first1=Antoni |editor1-last=Rozenberg |editor1-first=G. |editor2-last=Diekert |editor2-first=V. |title=The Book of Traces |date=1995 |publisher=World Scientific |location=Singapore |isbn=981-02-2058-8 |chapter-url=http://www.cas.mcmaster.ca/~cas724/2007/paper2.pdf |access-date=18 April 2021 |chapter=Introduction to Trace Theory}}{{rp|6}} Elements $x,y\; \backslash in\; \backslash Sigma$ are called dependent if $xDy$ holds, and independent, else (i.e. if $xIy$ holds).{{rp|6}}

Given a reliance alphabet $(\backslash Sigma,\; D,\; I)$, a symmetric and irreflexive relation $\backslash doteq$ can be defined on the free monoid $\backslash Sigma^*$ of all possible strings of finite length by: $x\; a\; b\; y\; \backslash doteq\; x\; b\; a\; y$ for all strings $x,\; y\; \backslash in\; \backslash Sigma^*$ and all independent symbols $a,\; b\; \backslash in\; I$. The equivalence closure of $\backslash doteq$ is denoted $\backslash equiv$ or $\backslash equiv\_\{(\backslash Sigma,\; D,\; I)\}$ and called $(\backslash Sigma,\; D,\; I)$-equivalence. Informally, $p\; \backslash 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 $\backslash equiv$ are called traces,{{rp|7–8}} and are studied in trace theory.