relation de dépendance

En informatique , et plus particulièrement en théorie de la concurrence , une relation de dépendance est une relation binaire symétrique et réflexive sur un domaine fini ${\displaystyle \Sigma <semantics><mrow><mstyle><mi>Σ</mi></mstyle></mrow><annotation>{\displaystyle \Sigma }</annotation></semantics></math><img src=$ ${\displaystyle D <semantics><mrow><mstyle><mi>D</mi></mstyle></mrow><annotation>{\displaystyle D}</annotation></semantics></math><img src=$

Si ${\displaystyle (a,b)\in D <semantics><mrow><mstyle><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>∈</mo><mi>D</mi></mstyle></mrow><annotation>{\displaystyle (a,b)\in D}</annotation></semantics></math><img src=$ ${\displaystyle (b,a)\in D <semantics><mrow><mstyle><mo>(</mo><mi>b</mi><mo>,</mo><mi>un</mi><mo>)</mo><mo>∈</mo><mi>D</mi></mstyle></mrow><annotation>{\displaystyle (b,a)\in D}</annotation></semantics></math><img src=$
Si ${\displaystyle a\in \Sigma <semantics><mrow><mstyle><mi>un</mi><mo>∈</mo><mi>Σ</mi></mstyle></mrow><annotation>{\displaystyle a\in \Sigma }</annotation></semantics></math><img src=$ ${\displaystyle (a,a)\in D <semantics><mrow><mstyle><mo>(</mo><mi>un</mi><mo>,</mo><mi>un</mi><mo>)</mo><mo>∈</mo><mi>D</mi></mstyle></mrow><annotation>{\displaystyle (a,a)\in D}</annotation></semantics></math><img src=$

En général, les relations de dépendance ne sont pas transitives ; elles généralisent donc la notion de relation d'équivalence en faisant abstraction de la transitivité.

${\displaystyle \Sigma <semantics><mrow><mstyle><mi>Σ</mi></mstyle></mrow><annotation>{\displaystyle \Sigma }</annotation></semantics></math><img src=$ ${\displaystyle D <semantics><mrow><mstyle><mi>D</mi></mstyle></mrow><annotation>{\displaystyle D}</annotation></semantics></math><img src=$ indépendance induite par ${\displaystyle D <semantics><mrow><mstyle><mi>D</mi></mstyle></mrow><annotation>{\displaystyle D}</annotation></semantics></math><img src=$ ${\displaystyle I <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle Je}</annotation></semantics></math><img src=$

{\displaystyle I=(\Sigma imes \Sigma )\setminus D <semantics><mrow><mstyle><mi>je</mi><mo>=</mo><mo>(</mo><mi>Σ</mi><mo>×</mo><mi>Σ</mi><mo>)</mo><mo>∖</mo><mi>D</mi></mstyle></mrow><annotation>{\displaystyle I=(\Sigma imes \Sigma )\setminus D}</annotation></semantics></math></span><img src=

Autrement dit, l'indépendance est l'ensemble de toutes les paires ordonnées qui ne sont pas dans ${\displaystyle D <semantics><mrow><mstyle><mi>D</mi></mstyle></mrow><annotation>{\displaystyle D}</annotation></semantics></math><img src=$ ${\displaystyle I <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle Je}</annotation></semantics></math><img src=$

{\displaystyle D=(\Sigma imes \Sigma )\setminus I <semantics><mrow><mstyle><mi>D</mi><mo>=</mo><mo>(</mo><mi>Σ</mi><mo>×</mo><mi>Σ</mi><mo>)</mo><mo>∖</mo><mi>je</mi></mstyle></mrow><annotation>{\displaystyle D=(\Sigma imes \Sigma )\setminus I}</annotation></semantics></math></span><img src=

est une relation de dépendance.

Le couple ${\displaystyle (\Sigma ,D) <semantics><mrow><mstyle><mo>(</mo><mi>Σ</mi><mo>,</mo><mi>D</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (\Sigma ,D)}</annotation></semantics></math><img src=$ alphabet concurrent . La paire ${\displaystyle (\Sigma ,I) <semantics><mrow><mstyle><mo>(</mo><mi>Σ</mi><mo>,</mo><mi>je</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (\Sigma ,I)}</annotation></semantics></math><img src=$ alphabet de l'indépendance ou l'alphabet de la confiance , mais ce terme peut aussi désigner le triple ${\displaystyle (\Sigma ,D,I) <semantics><mrow><mstyle><mo>(</mo><mi>Σ</mi><mo>,</mo><mi>D</mi><mo>,</mo><mi>je</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (\Sigma ,D,I)}</annotation></semantics></math><img src=$ ${\displaystyle I <semantics><mrow><mstyle><mi>je</mi></mstyle></mrow><annotation>{\displaystyle Je}</annotation></semantics></math><img src=$ ${\displaystyle D <semantics><mrow><mstyle><mi>D</mi></mstyle></mrow><annotation>{\displaystyle D}</annotation></semantics></math><img src=$ ${\displaystyle x,y\in \Sigma <semantics><mrow><mstyle><mi>x</mi><mo>,</mo><mi>y</mi><mo>∈</mo><mi>Σ</mi></mstyle></mrow><annotation>{\displaystyle x,y\in \Sigma }</annotation></semantics></math><img src=$ dépendants si ${\displaystyle xDy <semantics><mrow><mstyle><mi>x</mi><mi>D</mi><mi>y</mi></mstyle></mrow><annotation>{\displaystyle xDy}</annotation></semantics></math><img src=$ indépendant , sinon (c'est-à-dire si ${\displaystyle xIy <semantics><mrow><mstyle><mi>x</mi><mi>je</mi><mi>y</mi></mstyle></mrow><annotation>{\displaystyle xIy}</annotation></semantics></math><img src=$

Étant donné un alphabet de dépendance ${\displaystyle (\Sigma ,D,I) <semantics><mrow><mstyle><mo>(</mo><mi>Σ</mi><mo>,</mo><mi>D</mi><mo>,</mo><mi>je</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (\Sigma ,D,I)}</annotation></semantics></math><img src=$ ${\displaystyle \doteq <semantics><mrow><mstyle><mo>≐</mo></mstyle></mrow><annotation>{\displaystyle \doteq }</annotation></semantics></math><img src=$ ${\displaystyle \Sigma ^{* <semantics><mrow><mstyle><msup><mi>Σ</mi><mrow><mo>∗</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle \Sigma ^{*}}</annotation></semantics></math><img src=$ ${\displaystyle xaby\doteq xbay <semantics><mrow><mstyle><mi>x</mi><mi>un</mi><mi>b</mi><mi>y</mi><mo>≐</mo><mi>x</mi><mi>b</mi><mi>un</mi><mi>y</mi></mstyle></mrow><annotation>{\displaystyle xaby\doteq xbay}</annotation></semantics></math><img src=$ ${\displaystyle x,y\in \Sigma ^{* <semantics><mrow><mstyle><mi>x</mi><mo>,</mo><mi>y</mi><mo>∈</mo><msup><mi>Σ</mi><mrow><mo>∗</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle x,y\in \Sigma ^{*}}</annotation></semantics></math><img src=$ ${\displaystyle a,b\in I <semantics><mrow><mstyle><mi>un</mi><mo>,</mo><mi>b</mi><mo>∈</mo><mi>je</mi></mstyle></mrow><annotation>{\displaystyle a,b\in I}</annotation></semantics></math><img src=$ ${\displaystyle \doteq <semantics><mrow><mstyle><mo>≐</mo></mstyle></mrow><annotation>{\displaystyle \doteq }</annotation></semantics></math><img src=$ ${\displaystyle \equiv <semantics><mrow><mstyle><mo>≡</mo></mstyle></mrow><annotation>{\displaystyle \equiv }</annotation></semantics></math><img src=$ ${\displaystyle \equiv _{(\Sigma ,D,I) <semantics><mrow><mstyle><msub><mo>≡</mo><mrow><mo>(</mo><mi>Σ</mi><mo>,</mo><mi>D</mi><mo>,</mo><mi>je</mi><mo>)</mo></mrow></msub></mstyle></mrow><annotation>{\displaystyle \equiv _{(\Sigma ,D,I)}}</annotation></semantics></math><img src=$ ${\displaystyle (\Sigma ,D,I) <semantics><mrow><mstyle><mo>(</mo><mi>Σ</mi><mo>,</mo><mi>D</mi><mo>,</mo><mi>je</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (\Sigma ,D,I)}</annotation></semantics></math><img src=$ ${\displaystyle p\equiv q <semantics><mrow><mstyle><mi>p</mi><mo>≡</mo><mi>q</mi></mstyle></mrow><annotation>{\displaystyle p\equiv q}</annotation></semantics></math><img src=$ ${\displaystyle p <semantics><mrow><mstyle><mi>p</mi></mstyle></mrow><annotation>{\displaystyle p}</annotation></semantics></math><img src=$ ${\displaystyle q <semantics><mrow><mstyle><mi>q</mi></mstyle></mrow><annotation>{\displaystyle q}</annotation></semantics></math><img src=$ ${\displaystyle \equiv <semantics><mrow><mstyle><mo>≡</mo></mstyle></mrow><annotation>{\displaystyle \equiv }</annotation></semantics></math><img src=$

Exemples

Étant donné l'alphabet ${\displaystyle \Sigma =\{a,b,c\ <semantics><mrow><mstyle><mi>Σ</mi><mo>=</mo><mo>{</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \Sigma =\{a,b,c\}}</annotation></semantics></math><img src=$ ${\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\ <semantics><mrow><mstyle><mi>D</mi><mo>=</mo><mo>{</mo><mo>(</mo><mi>un</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>,</mo><mspace></mspace><mo>(</mo><mi>b</mi><mo>,</mo><mi>un</mi><mo>)</mo><mo>,</mo><mspace></mspace><mo>(</mo><mi>un</mi><mo>,</mo><mi>c</mi><mo>)</mo><mo>,</mo><mspace></mspace><mo>(</mo><mi>c</mi><mo>,</mo><mi>un</mi><mo>)</mo><mo>,</mo><mspace></mspace><mo>(</mo><mi>un</mi><mo>,</mo><mi>un</mi><mo>)</mo><mo>,</mo><mspace></mspace><mo>(</mo><mi>b</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>,</mo><mspace></mspace><mo>(</mo><mi>c</mi><mo>,</mo><mi>c</mi><mo>)</mo><mo>}</mo></mstyle></mrow><annotation>{\displaystyle D=\{(a,b),\,(b,a),\,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}}</annotation></semantics></math><img src=$

L'indépendance correspondante est ${\displaystyle I=\{(b,c),\,(c,b)\ <semantics><mrow><mstyle><mi>je</mi><mo>=</mo><mo>{</mo><mo>(</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>)</mo><mo>,</mo><mspace></mspace><mo>(</mo><mi>c</mi><mo>,</mo><mi>b</mi><mo>)</mo><mo>}</mo></mstyle></mrow><annotation>{\displaystyle I=\{(b,c),\,(c,b)\}}</annotation></semantics></math><img src=$ ${\displaystyle b,c <semantics><mrow><mstyle><mi>b</mi><mo>,</mo><mi>c</mi></mstyle></mrow><annotation>{\displaystyle b,c}</annotation></semantics></math><img src=$ ${\displaystyle a,b <semantics><mrow><mstyle><mi>un</mi><mo>,</mo><mi>b</mi></mstyle></mrow><annotation>{\displaystyle a,b}</annotation></semantics></math><img src=$ ${\displaystyle acbba <semantics><mrow><mstyle><mi>un</mi><mi>c</mi><mi>b</mi><mi>b</mi><mi>un</mi></mstyle></mrow><annotation>{\displaystyle acbba}</annotation></semantics></math><img src=$ ${\displaystyle abcba <semantics><mrow><mstyle><mi>un</mi><mi>b</mi><mi>c</mi><mi>b</mi><mi>un</mi></mstyle></mrow><annotation>{\displaystyle abcba}</annotation></semantics></math><img src=$ ${\displaystyle abbca <semantics><mrow><mstyle><mi>un</mi><mi>b</mi><mi>b</mi><mi>c</mi><mi>un</mi></mstyle></mrow><annotation>{\displaystyle abbca}</annotation></semantics></math><img src=$