Monoid historii

W matematyce i informatyce monoid historii jest sposobem przedstawiania historii współbieżnie działających procesów komputerowych jako zbioru ciągów znaków , z których każdy reprezentuje indywidualną historię procesu. Monoid historii zapewnia zestaw prymitywów synchronizacji (takich jak blokady , muteksy lub łączenia wątków ) w celu zapewnienia punktów spotkania między zestawem niezależnie wykonujących się procesów lub wątków .

Monoidy historii występują w teorii obliczeń współbieżnych i zapewniają matematyczne podstawy niskiego poziomu dla rachunków procesów , takich jak CSP, język komunikacji procesów sekwencyjnych lub CCS, rachunek systemów komunikujących się . Monoidy historyczne zostały po raz pierwszy zaprezentowane przez MW Shields.

Monoidy historii są izomorficzne z monoidami śladowymi (wolne monoidy częściowo przemienne ) i z monoidem grafów zależności . Jako takie są obiektami wolnymi i uniwersalnymi . Monoid historii jest rodzajem półabelowego iloczynu kategorycznego w kategorii monoidów.

Monoidy produktowe i projekcja

Pozwalać

${\ Displaystyle A = (\ Sigma _ {1}, \ Sigma _ {2}, \ ldots, \ Sigma _ {n})}$

oznaczają n -krotkę (niekoniecznie rozłącznych parami) alfabetów ${\ displaystyle \ Sigma _ {k}}$ . Niech oznaczają wszystkie możliwe kombinacje jednego ciągu o skończonej długości z każdego alfabetu: ${\ Displaystyle P (A) }$

${\ Displaystyle P (A) = \ Sigma _ {1} ^ {*} \ razy \ Sigma _ {2} ^ {*} \ razy \cdots \times \Sigma _{n}^{*}}$

$indeksie$ W bardziej formalnym języku, $kartezjańskim$ iloczynem wolnych monoidów . górnym jest ) Skład monoidu produktu jest składowy, tak że np

${\ Displaystyle \ mathbf {u} = (u_ {1}, u_ {2}, \ ldots, u_ {n}) \,}$

I

${\ Displaystyle \ mathbf {v} = (v_ {1}, v_ {2}, \ ldots, v_ {n}) \,}$

Następnie

${\ Displaystyle \ mathbf {uv} = (u_ {1} v_ {1}, u_ {2} v_ {2}, \ ldots ,u_{n}v_{n})\,}$

dla wszystkich ${\ Displaystyle \ mathbf {u}, \ mathbf {v}}$ w ${\ Displaystyle P (A)}$ . Zdefiniuj alfabet unii

${\ Displaystyle \ Sigma = \ Sigma _ {1} \ kubek \ Sigma _ {2} \ kubek \ cdots \ kubek \ Sigma _ {n}. \,}$

(Unia tutaj jest sumą $niektórych$ , a nie sumą rozłączną .) Biorąc pod uwagę dowolny ciąg wybrać tylko litery w $displaystyle \ Sigma _ {k} ^ {*}}$${$ przy użyciu odpowiedniej projekcji ciągów ${\ Displaystyle \ pi _ {k}: \ Sigma ^ {*} \ do \ Sigma _ {k} ^{*}}$ . Rozkład _ ${\ Displaystyle \ pi: \ Sigma ^ {*} \ na P (A)}$ to mapowanie działające na ${\ Displaystyle w \ in \ Sigma ^ {*}}$ ze wszystkimi π ${\ displaystyle \ pi _ {k}}$ , dzieląc go na składniki w każdym wolnym monoidzie: π k {\ displaystyle \ pi _ {k}

${\ Displaystyle \ pi (w) \ mapsto (\ pi _ {1} (w), \ pi _ {2} (w), \ ldots, \ pi _ {n} (w)). \,}$

Historie

Dla każdego $Sigma$ nazywana $\ Displaystyle a$ elementarną historią a \ in } Służy jako funkcja wskaźnika włączenia litery a do alfabetu ${\ displaystyle \ Sigma _ {k}}$ . To jest,

${\ Displaystyle \ pi (a) = (a_ {1}, a_ {2}, \ ldots, a_ {n})}$

Gdzie

${\ Displaystyle a_ {k} = {\ rozpocząć {przypadki} a {\ mbox {jeśli}} a \ w \ Sigma _ {k} \\\ varepsilon {\ mbox {w przeciwnym razie}}. \ koniec {przypadków}}}$

Tutaj ${\ displaystyle \ varepsilon}$ oznacza pusty ciąg . Monoida historii $jest$$_$ monoidu podstawowe ${\ Displaystyle H (A) = \ {\ pi (a) | a \ in \ Sigma \} ^ {*}}$ (gdzie gwiazda w indeksie górnym to gwiazda Kleene zastosowana z komponentową definicją składu, jak podano powyżej) . Elementy ${\ displaystyle H (A)}$ nazywane są historiami globalnymi , a projekcje historii globalnej nazywane są historiami indywidualnymi .

Połączenie z informatyką

Użycie słowa historia w tym kontekście i połączenie z komputerami współbieżnymi można rozumieć w następujący sposób. Indywidualna historia jest zapisem sekwencji stanów procesu (lub wątku lub maszyny ); alfabet $.$ zbiorem stanów

Litera występująca w dwóch lub więcej alfabetach służy jako prymityw synchronizacji między różnymi indywidualnymi historiami. Oznacza to, że jeśli taki list pojawia się w jednej indywidualnej historii, musi również wystąpić w innej historii i służy do „powiązania” lub „spotkania” ich razem.

Rozważmy na przykład ${\ Displaystyle \ Sigma _ {1} = \ {a, b, c \}}$ i ${\ Displaystyle \ Sigma _{2}=\{a,d,e\}}$ . $c, d, e \}}$ za . Podstawowe historie to ${\ Displaystyle (a, a)}$ , ${\ Displaystyle (b, \ varepsilon)}$ , ${\ Displaystyle (c, \ varepsilon)}$ , ${\ Displaystyle (\ varepsilon, d)}$ i ${\ Displaystyle (\ varepsilon, e)}$ . W tym przykładzie indywidualna historia pierwszego procesu może wyglądać następująco $b$$},$ podczas gdy indywidualna historia drugiego komputera może . Obie te ${\ Displaystyle bcbddcced}$ historie są reprezentowane przez historię globalną , ponieważ rzutowanie tego ciągu na poszczególne alfabety daje indywidualne historie. W historii globalnej można uznać , że litery ${\ displaystyle$ do $} dojeżdżają do pracy z literami$${\ displaystyle d}$ i ${\ displaystyle e}$ , w tym sensie, że można je uporządkować bez zmiany poszczególnych historii. Taka komutacja jest po prostu stwierdzeniem, że pierwszy i drugi proces przebiegają jednocześnie i są względem siebie nieuporządkowane; nie wymienili (jeszcze) żadnych wiadomości ani nie przeprowadzili żadnej synchronizacji.

Litera służy jako prymityw synchronizacji, ponieważ jej wystąpienie oznacza miejsce zarówno w historii globalnej, jak i indywidualnej, którego nie można $przemieścić$$\ displaystyle e}$$gdy$ litery mogą być ponownie uporządkowane poza $,$ mi $nie$$można$ zmienić . Tak więc historia świata ${\ displaystyle bcdabe}$ i historia globalna $bdcaeb}$ obie mają indywidualne historie ${\ displaystyle bcab}$ i ${\ displaystyle dae}$ , co wskazuje, że wykonanie $displaystyle$ może się zdarzyć przed lub po do $c}$ . Jednak litera synchronizuje się, więc $\ displaystyle a}$ gwarantuje, że nastąpi to po $,$ że $displaystyle$$w$ innym procesie niż $c}$ .

Nieruchomości

Monoid historyczny jest izomorficzny z monoidem śladowym i jako taki jest rodzajem półabelowego iloczynu kategorycznego w kategorii monoidów. $_$ historii _ izomorficzny z monoidem śladowym z relacją zależności ${\ Displaystyle \ mathbb {M} (D)}$ podane przez

${\ Displaystyle D = \ lewo (\ Sigma _ {1} \ razy \ Sigma _ {1} \ prawej) \ kubek \ lewo (\ Sigma _ {2} \ razy \ Sigma _ {2} \ prawej) \ kubek \ cdots \cup \left(\Sigma _{n}\times \Sigma _{n}\right).}$

$displaystyle \Sigma _{j}}$ litery alfabetu można przemiennie uporządkować poza literami alfabetu $_ {k}}$$Sigma$ , chyba że są to litery występujące w obu alfabetach. Tak więc ślady są dokładnie historiami globalnymi i vice versa.

$uwagę$ dowolny monoid śladowy $\ Displaystyle \ Sigma _ {a, b} = \ {a, b \}}$ izomorficzny monoid historii, biorąc sekwencję alfabetów gdzie ${\ Displaystyle (a, b)}$$obejmuje$ wszystkie pary .

Notatki

•   Antoni Mazurkiewicz, „Wstęp do teorii śladów”, s. 3–41, w: Księga śladów , V. Diekert, G. Rozenberg, wyd. (1995) World Scientific, Singapur ISBN 981-02-2058-8
• Volker Diekert, Yves Métivier, „ Partial Commutation and Traces ”, w G. Rozenberg i A. Salomaa , redaktorzy, Handbook of Formal Languages , tom. 3 , Poza słowami, strony 457–534. Springer-Verlag, Berlin, 1997.