Algebra procesów komunikowania się

Algebra procesów komunikowania się (ACP) to algebraiczne podejście do wnioskowania o systemach współbieżnych . Należy do rodziny matematycznych teorii współbieżności znanych jako algebry procesów lub rachunki procesów . ACP został początkowo opracowany przez Jana Bergstrę i Jana Willema Klopa w 1982 roku w ramach próby zbadania rozwiązań niestrzeżonych równań rekurencyjnych. W większym stopniu niż inne przełomowe rachunki procesów ( CCS i CSP ), rozwój ACP koncentrował się na algebrze procesów i miał na celu stworzenie abstrakcyjnego, uogólnionego systemu aksjomatycznego dla procesów. W rzeczywistości termin algebra procesów został ukuty podczas badań co doprowadziło do AKP.

Nieformalny opis

ACP jest zasadniczo algebrą w sensie algebry uniwersalnej . Ta algebra jest sposobem opisywania systemów za pomocą wyrażeń procesów algebraicznych, które definiują składy innych procesów lub pewnych elementów pierwotnych.

prymitywy

${\ Displaystyle {\ mathit {a, b, c,...}}})$ , atomowe działania ( jako prymitywy. Niektóre akcje mają specjalne znaczenie, na $przykład$ akcja , która reprezentuje $stagnację$ , oraz akcja , która reprezentuje cichą akcję (akcje abstrakcyjne, które nie mają określonej tożsamości).

Operatory algebraiczne

Akcje można łączyć, tworząc procesy przy użyciu różnych operatorów. Operatory te można z grubsza sklasyfikować jako zapewniające podstawową algebrę procesów , współbieżność i komunikację .

• Wybór i sekwencjonowanie - najbardziej podstawowymi operatorami algebraicznymi są $($ alternatywny ( $)$ , który zapewnia wybór między akcjami, oraz operator sekwencjonowania ) , określa kolejność działań . Na przykład proces

${\ Displaystyle (a + b) \ cdot c}$

najpierw wybiera wykonanie albo ${\ Displaystyle {\ mathit {a}}}$ lub ${\ Displaystyle {\ mathit {b}}}$ , a następnie wykonuje akcję ${\ displaystyle {\ mathit {c}}}$ . Sposób $dokonania$ wyboru między $nieokreślony$ nie ma znaczenia i pozostaje Zauważ, że kompozycja alternatywna jest przemienna, ale kompozycja sekwencyjna nie (ponieważ czas płynie do przodu).

• Współbieżność – aby umożliwić opis współbieżności, ACP zapewnia operatory scalania i lewego scalania . Operator scalania, ${\ displaystyle \ vert \ vert}$ , reprezentuje równoległą kompozycję dwóch procesów, których poszczególne działania są przeplatane. Lewy operator scalania, ${\ displaystyle \ vert \ lfloor}$ jest operatorem pomocniczym o semantyce podobnej do scalania, ale zobowiązuje się zawsze wybierać swój początkowy krok z procesu po lewej stronie. Na przykład proces

${\ Displaystyle (a \ cdot b) \ vert \ vert (c \ cdot d)}$

może wykonywać czynności ${\ Displaystyle a, b, c, d}$ w dowolnym z sekwencje $, acbd, acdb, cabd, cadb, cdab}$ . Z drugiej strony proces

${\ Displaystyle (a \ cdot b) \ vert \ lfloor (c \ cdot d)}$

może wykonywać tylko sekwencje $\ Displaystyle abcd, acbd, acdb},$$ponieważ$ operatory lewego scalania zapewniają, że akcja jako pierwsza.

• Komunikacja — interakcja (lub komunikacja) między procesami jest reprezentowana za pomocą binarnego operatora komunikacji, ${\ displaystyle \ vert}$ . Na przykład działania i jako $d)}$ i zapisywanie elementu danych ${\ Displaystyle d \ w D = \ {1,2,3, \ ldots \}}$$r ($ odpowiednio. Wtedy proces

${\ Displaystyle \ lewo (\ suma _ {d \ w D} r (d) \ cdot y \ prawo) \ vert (w (1) \ cdot z)} przekaże$

wartość ${$$\ displaystyle 1} displaystyle {\ mathit {d$ prawego procesu składowego do lewego procesu składowego ( tj. $identyfikator$ jest $powiązany$ z wartością wolne wystąpienia $}}$ } w procesie przyjmuje tę wartość $)$ , a następnie zachowuje się jak połączenie i $}$${\ Displaystyle {\ mathit {z}}}$ .

• Abstrakcja - operator abstrakcji , jest sposobem na „ukrycie” pewnych działań i traktowanie ich jako zdarzeń wewnętrznych w $.$ Akcje abstrakcyjne są konwertowane na cichą akcję krokową ${\ displaystyle \ tau}$ do

• . W niektórych przypadkach te ciche kroki można również usunąć z wyrażenia procesu w ramach procesu abstrakcji.

$) \ cdot c) = (a + b) \ cdot \ tau }$

, które w tym przypadku można zredukować do

$a + b},$

ponieważ zdarzenie $displaystyle$ jest już obserwowalne i nie ma obserwowalne efekty.

Definicja formalna

ACP zasadniczo przyjmuje aksjomatyczne, algebraiczne podejście do formalnej definicji swoich różnych operatorów. Przedstawione poniżej aksjomaty obejmują pełny system aksjomatyczny dla AKP _$.$ ACP z abstrakcją)

Podstawowa algebra procesu

Korzystając z alternatywnych i sekwencyjnych operatorów kompozycji, ACP definiuje podstawową algebrę procesów , która spełnia aksjomaty

${\ Displaystyle {\ rozpocząć {macierz} x + y & = & y + x \\ (x + y) + z & = & x + (y + z) \\ x + x & = & x \\(x+y)\cdot z&=&(x\cdot z)+(y\cdot z)\\(x\cdot y)\cdot z&=&x\cdot (y\cdot z)\end{macierz }}}$

Impas

Poza podstawową algebrą dwa dodatkowe aksjomaty definiują relacje między operatorami alternatywnymi i operatorami sekwencjonowania oraz działaniem impasu . ${\ displaystyle \ delta}$

${\ Displaystyle {\ rozpocząć {macierz} \ delta + x & = & x \\\ delta \ cdot x & = & \ delta \ koniec {macierz}}}$

Współbieżność i interakcja

Aksjomaty związane z operatorami scalania, lewego scalania i komunikacji to

${\ Displaystyle {\ rozpocząć {macierz} x \ vert \ vert y& = & x \ vert \ lfloor y + y \ vert \ lfloor x + x \ vert y \\ a \ cdot x \ vert \ lfloor y & = i a \ cdot (x\vert \vert y)\\a\vert \lfloor y&=&a\cdot y\\(x+y)\vert \lfloor z&=&(x\vert \lfloor z)+(y\vert \lfloor z)\\a\cdot x\vert b&=&(a\vert b)\cdot x\\a\vert b\cdot x&=&(a\vert b)\cdot x\\a\cdot x\vert b\cdot y&=&(a\vert b)\cdot (x\vert \vert y)\\(x+y)\vert z&=&x\vert z+y\vert z\\x\vert (y+ z)&=&x\vert y+x\vert z\end{macierz}}}$

Gdy operator komunikacji jest stosowany do samych działań, a nie do procesów, jest interpretowany jako funkcja binarna od działań do działań, ${\ Displaystyle \ vert: A \ razy A \ rightarrow A}$ . Definicja tej funkcji definiuje możliwe interakcje między procesami - te pary akcji, które nie stanowią interakcji, są odwzorowywane na akcję zakleszczenia, $podczas$ dozwolone pary interakcji są odwzorowywane na odpowiadające im pojedyncze akcje reprezentujące występowanie interakcja. Na przykład funkcja komunikacyjna może to określić

${\ Displaystyle a \ vert a \ rightarrow c}$

co wskazuje, że udana interakcja ${\ displaystyle a \ vert a}$ zostanie zredukowany do działania do $\ displaystyle c}$ . ACP zawiera również operator enkapsulacji dla niektórych , $H$ służy do konwersji nieudanych prób komunikacji (tj. elementów $subseteq A}$$\ displaystyle$ , które nie zostały zredukowane przez funkcję komunikacyjną) do działania impasu. Aksjomaty związane z funkcją komunikacyjną i operatorem enkapsulacji to

${\ Displaystyle {\ rozpocząć {macierz} a \ vert b & = & b \ vert a \\ (a \ vert b) \ vert c & = & a \ vert (b \ vert c)\\a\vert \delta &=&\delta \\\częściowo _{H}(a)&=&a{\mbox{ if }}a\notin H\\\częściowo _{H}(a) &=&\delta {\mbox{ if }}a\in H\\\częściowe _{H}(x+y)&=&\częściowe _{H}(x)+\częściowe _{H}(y )\\\częściowa _{H}(x\cdot y)&=&\częściowa _{H}(x)\cdot \częściowa _{H}(y)\\\end{macierz}}}$

Abstrakcja

Aksjomaty związane z operatorem abstrakcji to

${\ Displaystyle {\ rozpocząć {matrix} \ tau _ {I} (\ tau) & = & \ tau \\\ tau _ {I} (a) & = & a {\ mbox {jeśli}} a \ nie ja \\\tau _{I}(a)&=&\tau {\mbox{ if }}a\in I\\\tau _{I}(x+y)&=&\tau _{I}( x)+\tau _{I}(y)\\\tau _{I}(x\cdot y)&=&\tau _{I}(x)\cdot \tau _{I}(y)\ \\częściowa _{H}(\tau )&=&\tau \\x\cdot \tau &=&x\\\tau \cdot x&=&\tau \cdot x+x\\a\cdot (\tau \cdot x+y)&=&a\cdot (\tau \cdot x+y)+a\cdot x\\\tau \cdot x\vert \lfloor y&=&\tau \cdot (x\vert \vert y )\\\tau \vert \lfloor x&=&\tau \cdot x\\\tau \vert x&=&\delta \\x\vert \tau &=&\delta \\\tau \cdot x\vert y& =&x\vert y\\x\vert \tau \cdot y&=&x\vert y\end{macierz}}}$

Zauważ, że akcja a na powyższej liście może przyjąć wartość δ (ale oczywiście δ nie może należeć do zbioru abstrakcji I ).

Formalizmy pokrewne

ACP służył jako podstawa lub inspiracja dla kilku innych formalizmów, które można wykorzystać do opisu i analizy systemów współbieżnych, w tym:

• PSF
• μCRL
• mCRL2
• HyPA — algebra procesów dla systemów hybrydowych