Relacja zależności - Dependency relation
W informatyce , w szczególności w teorii współbieżności , relacja zależności jest relacją binarną, która jest skończona, symetryczna i zwrotna ; czyli skończoną relację tolerancji . Oznacza to, że jest to skończony zbiór par uporządkowanych , taki, że
- Jeśli to (symetrycznie)
- Jeżeli jest elementem zbioru, na którym relacja jest zdefiniowana, to (refleksyjna)
Ogólnie relacje zależności nie są przechodnie ; w ten sposób uogólniają pojęcie relacji równoważności , odrzucając przechodniość.
Jeśli oznacza alfabet, na którym jest zdefiniowany, to indukowana przez niego niezależność jest relacją binarną
Oznacza to, że niezależność jest zbiorem wszystkich uporządkowanych par, które nie są w . Relacja niezależności jest symetryczna i niezwrotna. I odwrotnie, biorąc pod uwagę dowolną symetryczną i niezwrotną relację na skończonym alfabecie, relacja
jest relacją zależności.
Para nazywa się współbieżnym alfabetem . Para ta nazywana jest alfabetem niezależności lub alfabetem zależności , ale termin ten może również odnosić się do trójki (z indukowanym przez ). Elementy są nazywane zależnymi if hold i niezależnymi , else (tj. if hold).
Mając alfabet zależności , symetryczną i niezwrotną relację można zdefiniować na swobodnym monoidzie wszystkich możliwych ciągów o skończonej długości przez: dla wszystkich ciągów i wszystkich niezależnych symboli . Zamknięcie równoważność z oznaczamy lub i nazywany -equivalence. Nieformalnie, przechowuje, jeśli łańcuch może zostać przekształcony przez skończoną sekwencję zamian sąsiednich niezależnych symboli. Do klas równoważności z nazywane są ślady , i są badane w teorii śladowej .
Przykłady
Biorąc pod uwagę alfabet , możliwą relacją zależności jest , patrz rysunek.
Odpowiednia niezależność to . Wtedy np. symbole są od siebie niezależne, a np. są zależne. Ciąg jest równoważny do i do , ale do żadnego innego ciągu.