Dependency relation

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, in particular in <a href="/facts/Concurrency_(computer_science)/Ctnrrq4A">concurrency theory</a>, a dependency relation is a <a href="/facts/Binary_relation/r9BwGgaK">binary relation</a> on a finite domain 
 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
,: 4  <a href="/facts/Symmetric_relation/ekCWDIAH">symmetric</a>, and <a href="/facts/Reflexive_relation/NzTytEg9">reflexive</a>;: 6  i.e. a finite <a href="/facts/Tolerance_relation/aG2u3sYz">tolerance relation</a>. That is, it is a finite set of <a href="/facts/Ordered_pair/EInLVI0r">ordered pairs</a> 
 
 
 
 D
 
 
 {\displaystyle D}
 
, such that

<ul><li>If 
 
 
 
 (
 a
 ,
 b
 )
 ∈
 D
 
 
 {\displaystyle (a,b)\in D}
 
 then 
 
 
 
 (
 b
 ,
 a
 )
 ∈
 D
 
 
 {\displaystyle (b,a)\in D}
 
 (symmetric)</li>
<li>If 
 
 
 
 a
 ∈
 Σ
 
 
 {\displaystyle a\in \Sigma }
 
, then 
 
 
 
 (
 a
 ,
 a
 )
 ∈
 D
 
 
 {\displaystyle (a,a)\in D}
 
 (reflexive)</li></ul>
In general, dependency relations are not <a href="/facts/Transitive_relation/9r90y50r">transitive</a>; thus, they generalize the notion of an <a href="/facts/Equivalence_relation/1MQ5rtkW">equivalence relation</a> by discarding transitivity.

 
 
 
 Σ
 
 
 {\displaystyle \Sigma }
 
 is also called the <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a> on which 
 
 
 
 D
 
 
 {\displaystyle D}
 
 is defined. The independency induced by 
 
 
 
 D
 
 
 {\displaystyle D}
 
 is the binary relation 
 
 
 
 I
 
 
 {\displaystyle I}

I
        =
        (
        Σ
        ×
        Σ
        )
        ∖
        D
      
    
    {\displaystyle I=(\Sigma \times \Sigma )\setminus D}

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

D
        =
        (
        Σ
        ×
        Σ
        )
        ∖
        I
      
    
    {\displaystyle D=(\Sigma \times \Sigma )\setminus I}

is a dependency relation.
The pair 
 
 
 
 (
 Σ
 ,
 D
 )
 
 
 {\displaystyle (\Sigma ,D)}
 
 is called the concurrent alphabet.: 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}
 
).: 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).: 6 
Given a reliance alphabet 
 
 
 
 (
 Σ
 ,
 D
 ,
 I
 )
 
 
 {\displaystyle (\Sigma ,D,I)}
 
, a symmetric and irreflexive relation 
 
 
 
 ≐
 
 
 {\displaystyle \doteq }
 
 can be defined on the <a href="/facts/Free_monoid/h3nPVjqr">free monoid</a> 
 
 
 
 
 Σ
 
 ∗
 
 
 
 
 {\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 <a href="/facts/Equivalence_closure/Ct6r2fJz">equivalence closure</a> 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 <a href="/facts/Equivalence_class/1d2sh0TB">equivalence classes</a> of 
 
 
 
 ≡
 
 
 {\displaystyle \equiv }
 
 are called <a href="/facts/Trace_monoid/Y7ShnaSE">traces</a>,: 7–8  and are studied in <a href="/facts/Trace_theory/bSpU6q8M">trace theory</a>.

Dependency relation open-in-new

Dependency relation