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

Relacja zależności.svg

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.

Bibliografia