Dependency relation

<h2 id="examples">Examples</h2>

<p>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.
</p><p>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.
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>IJsbrand Jan Aalbersberg and Grzegorz Rozenberg (Mar 1988). "Theory of traces". Theoretical Computer Science. 60 (1): 1–82. doi:10.1016/0304-3975(88)90051-5. <a href="https://doi.org/10.1016%2F0304-3975%2888%2990051-5" target="_blank">https://doi.org/10.1016%2F0304-3975%2888%2990051-5</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>IJsbrand Jan Aalbersberg and Grzegorz Rozenberg (Mar 1988). "Theory of traces". Theoretical Computer Science. 60 (1): 1–82. doi:10.1016/0304-3975(88)90051-5. <a href="https://doi.org/10.1016%2F0304-3975%2888%2990051-5" target="_blank">https://doi.org/10.1016%2F0304-3975%2888%2990051-5</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Vasconcelos, Vasco Thudichum (1992). Trace semantics for concurrent objects (MsC thesis). Keio University. CiteSeerX 10.1.1.47.7099. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory" (PDF). In Rozenberg, G.; Diekert, V. (eds.). The Book of Traces. Singapore: World Scientific. ISBN 981-02-2058-8. Retrieved 18 April 2021. <a href="981-02-2058-8" target="_blank">981-02-2058-8</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>IJsbrand Jan Aalbersberg and Grzegorz Rozenberg (Mar 1988). "Theory of traces". Theoretical Computer Science. 60 (1): 1–82. doi:10.1016/0304-3975(88)90051-5. <a href="https://doi.org/10.1016%2F0304-3975%2888%2990051-5" target="_blank">https://doi.org/10.1016%2F0304-3975%2888%2990051-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>IJsbrand Jan Aalbersberg and Grzegorz Rozenberg (Mar 1988). "Theory of traces". Theoretical Computer Science. 60 (1): 1–82. doi:10.1016/0304-3975(88)90051-5. <a href="https://doi.org/10.1016%2F0304-3975%2888%2990051-5" target="_blank">https://doi.org/10.1016%2F0304-3975%2888%2990051-5</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Dependency relation open-in-new

Dependency relation