Beroenderelation

För annan användning, se Beroende (disambiguation) .

Ej att förväxla med Dependence relation , som är en generalisering av begreppet linjärt beroende bland medlemmar i ett vektorrum.

Inom datavetenskap , i synnerhet inom samtidighetsteori , är en beroenderelation en binär relation på en finit domän $\Sigma$ , symmetrisk och reflexiv ; dvs en ändlig toleransrelation . Det vill säga, det är en ändlig uppsättning ordnade par $D$ , så att

• Om $(a,b)\in D$ så $(b,a)\in D$ (symmetrisk)
• Om $a\in \Sigma$ , då $(a,a)\in D$ (reflexiv)

I allmänhet är beroendeförhållanden inte transitiva ; sålunda generaliserar de föreställningen om en ekvivalensrelation genom att förkasta transitivitet.

$\Sigma$ kallas också alfabetet där $D$ definieras. Oberoendet som induceras av $D$ är den binära relationen $\displaystyle I}$ {

$I=(\Sigma \times \Sigma )\setminus D$

Det vill säga, oberoendet är mängden av alla ordnade par som inte finns i $D$ . Oberoenderelationen är symmetrisk och irreflexiv. Omvänt, givet varje symmetrisk och irreflexiv relation $I$ på ett ändligt alfabet, är relationen

$D=(\Sigma \times \Sigma )\setminus I$

är ett beroendeförhållande.

Paret $(\Sigma ,D)$ kallas det samtidiga alfabetet . Paret $(\Sigma ,I)$ kallas oberoendealfabetet eller reliance-alfabetet , men denna term kan också syfta på trippel $(\Sigma ,D ,I)$ (med $I$ inducerad av $D$ ). Elementen $x,y\in \Sigma$ kallas beroende om $xDy$ gäller, och oberoende , annars (dvs. om $xIy$ gäller).

Givet ett reliance-alfabet ${\displaystyle (\Sigma ,D,I)} , kan$ en symmetrisk och irreflexiv relation $\doteq$ definieras på den fria monoiden $\Sigma ^{*}$ av alla möjliga strängar av ändlig längd med: $xaby\doteq xbay$ för alla strängar $x,y\in \Sigma ^{*}$ och alla oberoende symboler $a,b\in I$ . Ekvivalensstängningen av $\doteq$ betecknas $\equiv$ eller ${(\Sigma ,D,I)}$ _ och anropas $(\Sigma ,D,I)$ -ekvivalens. Informellt $p\equiv q$ om strängen $p$ kan omvandlas till $q$ genom en ändlig sekvens av byten av intilliggande oberoende symboler. Ekvivalensklasserna för $\equiv }$ displaystyle kallas spår och studeras i spårteorin .

Exempel

Givet alfabetet $\Sigma =\{a,b,c\}$ , är en möjlig beroenderelation ${\displaystyle D=\{(a,b),\,(b,a), \,(a,c),\,(c,a),\,(a,a),\,(b,b),\,(c,c)\}} , se bild$ .

Motsvarande oberoende är $I=\{(b,c),\,(c,b)\}$ . Då är t.ex. symbolerna $b,c$ oberoende av varandra, och t.ex. $a,b$ är beroende. Strängen $acbba$ motsvarar $abcba$ och $abbca$ , men ingen annan sträng.