{{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 symmetric and reflexive<ref name="Aalbersberg.Rozenberg.1988" />{{rp|6}} binary relation on a finite domain <math>\Sigma</math>;<ref name="Aalbersberg.Rozenberg.1988">{{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 }}</ref>{{rp|4}} i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs <math>D</math>, such that
* If <math>(a,b)\in D</math> then <math>(b,a) \in D</math> (symmetric) * If <math>a \in \Sigma</math>, then <math>(a,a) \in D</math> (reflexive)
In general, dependency relations are not transitive; thus, they generalize the notion of an equivalence relation by discarding transitivity.
<math>\Sigma</math> is also called the alphabet on which <math>D</math> is defined. The '''independency''' induced by <math>D</math> is the binary relation <math>I</math>
:<math>I = (\Sigma \times \Sigma) \setminus D</math>
That is, the independency is the set of all ordered pairs that are not in <math>D</math>. The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation <math>I</math> on a finite alphabet, the relation
:<math>D = (\Sigma \times \Sigma) \setminus I</math>
is a dependency relation.
The pair <math>(\Sigma, D)</math> is called the '''concurrent alphabet'''.<ref>{{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}}</ref>{{rp|6}} The pair <math>(\Sigma, I)</math> is called the '''independency alphabet''' or '''reliance alphabet''', but this term may also refer to the triple <math>(\Sigma, D, I)</math> (with <math>I</math> induced by <math>D</math>).<ref>{{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}}</ref>{{rp|6}} Elements <math>x,y \in \Sigma</math> are called '''dependent''' if <math>xDy</math> holds, and '''independent''', else (i.e. if <math>xIy</math> holds).<ref name="Aalbersberg.Rozenberg.1988"/>{{rp|6}}
Given a reliance alphabet <math>(\Sigma, D, I)</math>, a symmetric and irreflexive relation <math>\doteq</math> can be defined on the free monoid <math>\Sigma^*</math> of all possible strings of finite length by: <math>x a b y \doteq x b a y</math> for all strings <math>x, y \in \Sigma^*</math> and all independent symbols <math>a, b \in I</math>. The equivalence closure of <math>\doteq</math> is denoted <math>\equiv</math> or <math>\equiv_{(\Sigma, D, I)}</math> and called <math>(\Sigma, D, I)</math>-equivalence. Informally, <math>p \equiv q</math> holds if the string <math>p</math> can be transformed into <math>q</math> by a finite sequence of swaps of adjacent independent symbols. The equivalence classes of <math>\equiv</math> are called traces,<ref name="Aalbersberg.Rozenberg.1988"/>{{rp|7–8}} and are studied in trace theory.
==Examples== right Given the alphabet <math>\Sigma=\{a,b,c\}</math>, a possible dependency relation is <math>D = \{ (a,b),\, (b,a),\, (a,c),\, (c,a),\, (a,a),\, (b,b),\, (c,c) \}</math>, see picture.
The corresponding independency is <math>I=\{(b,c),\,(c,b)\}</math>. Then e.g. the symbols <math>b,c</math> are independent of one another, and e.g. <math>a,b</math> are dependent. The string <math>a c b b a</math> is equivalent to <math>a b c b a</math> and to <math>a b b c a</math>, but to no other string.
==References== {{reflist}}
Category:Properties of binary relations