• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Relacja silnie konfluentna

    Przeczytaj także...
    Teoria grafów to dział matematyki i informatyki zajmujący się badaniem własności grafów. Informatyka rozwija także algorytmy wyznaczające pewne właściwości grafów. Algorytmy te stosuje się do rozwiązywania wielu zadań praktycznych, często w dziedzinach na pozór nie związanych z grafami.Postać normalna (ang. normal form) to pewna szczególna postać wyrażenia, która jest w pewnym sensie "równoważna" każdemu wyrażeniu z pewnego zbioru wyrażeń. Od postaci systemu zależy, jaki to zbiór i jaki jest sens tej "równoważności". Wyrażenie może mieć jedną postać normalną lub nie mieć jej wcale.
    Ciąg – w matematyce pojęcie oddające intuicję ponumerowania, czy też uporządkowania elementów zbioru. W zależności od rodzaju elementów zbioru stosuje się różne nazwy: w przypadku liczb mówi się o ciągach liczbowych, bądź bardziej precyzyjnie, np. w przypadku zbioru liczb całkowitych, rzeczywistych czy zespolonych, ciąg nazywa się wtedy odpowiednio ciągiem całkowitoliczbowym, rzeczywistym i zespolonym. Jeśli elementami zbioru są funkcje, to ciąg nazywa się ciągiem funkcyjnym. Ciąg powstały poprzez wybranie elementów innego ciągu nazywa się podciągiem.

    Relacja silnie konfluentna (lub po prostu relacja konfluentna) - relacja taka, że jeśli istnieje ciąg elementów będących w stosunku do siebie kolejno w relacji prowadzący od do oraz ciąg od do o tej samej własności, to istnieje takie , że istnieją ciągi elementów będących kolejno względem siebie w relacji z do oraz z do . Mówiąc językiem teorii grafów, jeśli się rozejdziemy, zawsze potrafimy się ponownie zejść.

    Relacja symetryczna – relacja, która jeśli zachodzi dla pary ( x , y ) {displaystyle (x,y)} , to zachodzi też dla pary ( y , x ) {displaystyle (y,x)} .Relacja słabo konfluentna to relacja taka, że dla dowolnych a , b , c {displaystyle a,b,c} takich że a {displaystyle a} jest w relacji z b {displaystyle b} i a {displaystyle a} jest w relacji z c {displaystyle c} , istnieją takie ciągi skończone zaczynające się odpowiednio od b {displaystyle b} i c {displaystyle c} , które mają wspólny element końcowy d {displaystyle d} .

    Każda relacja symetryczna jest silnie konfluentna – możemy bowiem wrócić do tą samą drogą jaką tam się znaleźliśmy. Dlatego też własność konfluencji jest "interesująca" tylko w przypadku relacji, które nie są symetryczne. Każda relacja silnie konfluentna jest słabo konfluentna.

    Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić.Relacja – w teorii mnogości dowolny podzbiór iloczynu kartezjańskiego skończonej liczby zbiorów; definicja ta oddaje intuicję pewnego związku, czy zależności między elementami wspomnianych zbiorów (elementy wspomnianych zbiorów pozostają w związku albo łączy je pewna zależność, czy też własność lub nie). Najważniejszymi relacjami są relacje dwuargumentowe, tj. między elementami pary zbiorów (opisane w osobnym artykule, w tym funkcje i działania jednoargumentowe); relacje jednoargumentowe to po prostu podzbiory pewnego zbioru.

    Systemy obliczeń[]

    Konfluencja jest pojęciem w teorii obliczeń – jeśli system dokonywania obliczeń jest silnie konfluentny, to niezależnie od kolejności wykonywania obliczeń zawsze dojdziemy do tego samego wyniku.

    Na przykład system złożony z liczb całkowitych, symbolu +, oraz reguły redukcji zastępującej parę liczb po obu stronach symbolu + ich sumą jest silnie konfluentny. Rozpatrzmy dwie redukcje:

  • 2 + 3 + 4 + 5 + 6 → 2 + 3 + 4 + 11
  • 2 + 3 + 4 + 5 + 6 → 5 + 4 + 5 + 6
  • Można je doprowadzić do tego samego wyniku:

  • 2 + 3 + 4 + 11 → 2 + 3 + 15 → 2 + 18 → 20
  • 5 + 4 + 5 + 6 → 9 + 5 + 6 → 14 + 6 → 20
  • Nie wyklucza to jednak sytuacji, w której obliczenia jedną metodą dadzą wynik, zaś drugą będą działać "w nieskończoność". Jednak jeśli zaczynamy stosując strategię, która działałaby "w nieskończoność", w każdym momencie możemy dojść do wyniku, jeśli zmienimy zdanie i to, do czego ta strategia doszła, zaczniemy redukować w inny sposób.

    Do ważniejszych twierdzeń rachunku lambda należy to, że zbiór redukcji α i β w rachunku lambda jest silnie konfluentny (twierdzenie Churcha-Rossera).

    Postać normalna[]

    Drugą właściwością systemów silnie konfluentnych jest unikalność postaci normalnych. Postać normalna to element, którego nie da się zredukować. Element ma postać normalną , jeśli istnieje ciąg redukcji z do . Element nie może mieć dwóch postaci normalnych, ponieważ musiałyby one redukować się do wspólnego wyrażenia, zaś postać normalna jest z definicji nieredukowalna. W dalszym ciągu element ten może jednak nie mieć żadnej postaci normalnej. W przedstawionym powyżej systemie postaciami normalnymi są samodzielne liczby bez żadnych znaków +.

    Bibliografia[]

  • Handbook of automated reasoning, Volume 1 By John Alan Robinson, Andreĭ Voronkov, strona 561. ISBN 9780444829498.
  • Handbook of Formal Languages: Beyond words By Grzegorz Rozenberg, Arto Salomaa, strona 281. ISBN 9783540606499.



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.03 sek.