From Wikipedia, the free encyclopedia
Binary relation in computer science
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 Σ {\displaystyle \Sigma } ,[1]: 4 symmetric, and reflexive;[1]: 6 i.e. a finite tolerance relation. That is, it is a finite set of ordered pairs D {\displaystyle D} , such that
In general, dependency relations are not transitive; thus, they generalize the notion of an equivalence relation by discarding transitivity.
Σ {\displaystyle \Sigma } is also called the alphabet on which D {\displaystyle D} is defined. The independency induced by D {\displaystyle D} is the binary relation I {\displaystyle I}
That is, the independency is the set of all ordered pairs that are not in D {\displaystyle D} . The independency relation is symmetric and irreflexive. Conversely, given any symmetric and irreflexive relation I {\displaystyle I} on a finite alphabet, the relation
is a dependency relation.
The pair ( Σ , D ) {\displaystyle (\Sigma ,D)} is called the concurrent alphabet.[2]: 6 The pair ( Σ , I ) {\displaystyle (\Sigma ,I)} is called the independency alphabet or reliance alphabet, but this term may also refer to the triple ( Σ , D , I ) {\displaystyle (\Sigma ,D,I)} (with I {\displaystyle I} induced by D {\displaystyle D} ).[3]: 6 Elements x , y ∈ Σ {\displaystyle x,y\in \Sigma } are called dependent if x D y {\displaystyle xDy} holds, and independent, else (i.e. if x I y {\displaystyle xIy} holds).[1]: 6
Given a reliance alphabet ( Σ , D , I ) {\displaystyle (\Sigma ,D,I)} , a symmetric and irreflexive relation ≐ {\displaystyle \doteq } can be defined on the free monoid Σ ∗ {\displaystyle \Sigma ^{*}} of all possible strings of finite length by: x a b y ≐ x b a y {\displaystyle xaby\doteq xbay} for all strings x , y ∈ Σ ∗ {\displaystyle x,y\in \Sigma ^{*}} and all independent symbols a , b ∈ I {\displaystyle a,b\in I} . The equivalence closure of ≐ {\displaystyle \doteq } is denoted ≡ {\displaystyle \equiv } or ≡ ( Σ , D , I ) {\displaystyle \equiv _{(\Sigma ,D,I)}} and called ( Σ , D , I ) {\displaystyle (\Sigma ,D,I)} -equivalence. Informally, p ≡ q {\displaystyle p\equiv q} holds if the string p {\displaystyle p} can be transformed into q {\displaystyle q} by a finite sequence of swaps of adjacent independent symbols. The equivalence classes of ≡ {\displaystyle \equiv } are called traces,[1]: 7–8 and are studied in trace theory.
Given the alphabet Σ = { a , b , c } {\displaystyle \Sigma =\{a,b,c\}} , a possible dependency relation is D = { ( a , b ) , ( b , a ) , ( a , c ) , ( c , a ) , ( a , a ) , ( b , b ) , ( c , c ) } {\displaystyle 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 ) } {\displaystyle I=\{(b,c),\,(c,b)\}} . Then e.g. the symbols b , c {\displaystyle b,c} are independent of one another, and e.g. a , b {\displaystyle a,b} are dependent. The string a c b b a {\displaystyle acbba} is equivalent to a b c b a {\displaystyle abcba} and to a b b c a {\displaystyle abbca} , but to no other string.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4