Dependency relation

In computer science, in particular in concurrency theory, a dependency relation is a symmetric and reflexive binary relation on a finite domain \Sigma ; 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 \times \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 relation : D = (\Sigma \times \Sigma) \setminus I is a dependency relation. The pair (\Sigma, D) is called the concurrent alphabet. 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 ). Elements x,y \in \Sigma are called dependent if xDy holds, and independent, else (i.e. if xIy holds).…

In computer science, in particular in concurrency theory, a dependency relation is a symmetric and reflexive binary relation on a finite domain \Sigma ; 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 \times \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 relation D = (\Sigma \times \Sigma) \setminus I is a dependency relation. The pair (\Sigma, D) is called the concurrent alphabet. 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 ). Elements x,y \in \Sigma are called dependent if xDy holds, and independent, else (i.e. if xIy holds). Given a reliance alphabet (\Sigma, D, I) , a symmetric and irreflexive relation \doteq can be defined on the free monoid \Sigma^* of all possible strings of finite length by: x a b y \doteq x b a y for all strings x, y \in \Sigma^* and all independent symbols a, b \in I . The equivalence closure of \doteq is denoted \equiv or \equiv_{(\Sigma, D, I)} 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, and are studied in trace theory. ==Examples== Given 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. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1330111201 under CC BY-SA 4.0; modifications have been made.