Relația de dependență - Dependency relation

În informatică , în special în teoria concurenței , o relație de dependență este o relație binară care este finită, simetrică și reflexivă ; adică o relație de toleranță finită . Adică este un set finit de perechi ordonate , astfel încât ${\ displaystyle D}$

• Dacă atunci (simetric)${\ displaystyle (a, b) \ în D}$${\ displaystyle (b, a) \ în D}$
• Dacă este un element al mulțimii pe care este definită relația, atunci (reflexiv)${\ displaystyle a}$${\ displaystyle (a, a) \ în D}$

În general, relațiile de dependență nu sunt tranzitive ; astfel, ei generalizează noțiunea de relație de echivalență prin eliminarea tranzitivității.

Dacă denotă alfabetul pe care este definit, atunci independența indusă de este relația binară${\ displaystyle \ Sigma}$${\ displaystyle D}$${\ displaystyle D}$${\ displaystyle I}$

${\ displaystyle I = (\ Sigma \ times \ Sigma) \ setminus D}$

Adică, independența este ansamblul tuturor perechilor ordonate care nu se află în . Relația de independență este simetrică și ireflexivă. Dimpotrivă, având în vedere orice relație simetrică și ireflexivă pe un alfabet finit, relația ${\ displaystyle D}$${\ displaystyle I}$

${\ displaystyle D = (\ Sigma \ times \ Sigma) \ setminus I}$

este o relație de dependență.

Perechea se numește alfabet concurent . Perechea se numește alfabet de independență sau alfabet de dependență , dar acest termen se poate referi și la triplu (cu indus de ). Elementele sunt numite dependente dacă deține, și independente , altfel (adică dacă deține). ${\ displaystyle (\ Sigma, D)}$${\ displaystyle (\ Sigma, I)}$${\ displaystyle (\ Sigma, D, I)}$${\ displaystyle I}$${\ displaystyle D}$${\ displaystyle x, y \ in \ Sigma}$${\ displaystyle xDy}$${\ displaystyle xIy}$

Având în vedere un alfabet de dependență , o relație simetrică și ireflexivă poate fi definită pe monoidul liber al tuturor șirurilor posibile de lungime finită prin: pentru toate șirurile și toate simbolurile independente . Închidere de echivalență a se notează sau și numit -equivalence. În mod informal, reține dacă șirul poate fi transformat într- o secvență finită de swapuri de simboluri independente adiacente. În clasele de echivalență ale sunt numite urme , și sunt studiate în teoria urme . ${\ displaystyle (\ Sigma, D, I)}$${\ displaystyle \ doteq}$ ${\ displaystyle \ Sigma ^ {*}}$${\ displaystyle xaby \ doteq xbay}$${\ displaystyle x, y \ in \ Sigma ^ {*}}$${\ displaystyle a, b \ in I}$${\ displaystyle \ doteq}$${\ displaystyle \ equiv}$${\ displaystyle \ equiv _ {(\ Sigma, D, I)}}$${\ displaystyle (\ Sigma, D, I)}$${\ displaystyle p \ equiv q}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle \ equiv}$

Exemple

Având în vedere alfabetul , o posibilă relație de dependență este , a se vedea imaginea. ${\ displaystyle \ Sigma = \ {a, b, c \}}$${\ displaystyle D = \ {(a, b), \, (b, a), \, (a, c), \, (c, a), \, (a, a), \, (b, b), \, (c, c) \}}$

Independența corespunzătoare este . Apoi, de exemplu, simbolurile sunt independente unele de altele și, de exemplu, sunt dependente. Șirul este echivalent cu și cu , dar cu niciun alt șir. ${\ displaystyle I = \ {(b, c), \, (c, b) \}}$${\ displaystyle b, c}$${\ displaystyle a, b}$${\ displaystyle acbba}$${\ displaystyle abcba}$${\ displaystyle abbca}$

Referințe