Komunikująca się maszyna skończona

W informatyce komunikująca się maszyna skończona to maszyna skończona oznaczona operacjami „odbierz” i „wyślij” w pewnym alfabecie kanałów. Zostały one wprowadzone przez Branda i Zafiropulo i mogą być używane jako model współbieżnych procesów, takich jak sieci Petriego . Komunikujące się maszyny skończone są często używane do modelowania protokołów komunikacyjnych, ponieważ umożliwiają wykrywanie głównych błędów projektowych protokołów, w tym ograniczeń, zakleszczeń i nieokreślonych odbiorów.

Zaletą komunikowania się maszyn skończonych jest to, że umożliwiają one decydowanie o wielu właściwościach w protokołach komunikacyjnych, wykraczających poza poziom samego wykrywania takich właściwości. Ta zaleta wyklucza potrzebę pomocy człowieka lub ograniczenia w ogólności.

Komunikowanie się maszyn o skończonych stanach może być potężniejsze niż automaty o skończonych stanach w sytuacjach, w których opóźnienie propagacji nie jest pomijalne (tak, że kilka komunikatów może być przesyłanych jednocześnie) oraz w sytuacjach, w których naturalne jest opisanie stron protokołu i medium komunikacyjnego jako odrębne podmioty.

Komunikująca się hierarchiczna maszyna stanów

Hierarchiczne maszyny stanowe to skończone maszyny stanowe, których stany mogą być innymi maszynami. Ponieważ komunikująca się skończona maszyna stanów charakteryzuje się współbieżnością, najbardziej zauważalną cechą komunikującej się hierarchicznej maszyny stanów jest współistnienie hierarchii i współbieżności. Zostało to uznane za bardzo odpowiednie, ponieważ oznacza silniejszą interakcję wewnątrz maszyny.

Udowodniono jednak, że współistnienie hierarchii i współbieżności wewnętrznie kosztuje włączenie języka, równoważność języka i całą uniwersalność.

Definicja

Protokół

Dla dowolnej dodatniej liczby całkowitej $)$ z procesem ( ${(S_ {i}) _ {i = 1} ^ {N}, \ (o_ {i}) _{i=1}^{N},\ (M_{i,j})_{i,j=1}^{N},\ ({\mathtt {succ}})_{i=1}^ {N}\}}$$jest$ poczwórny z:

• $}$$}$ , sekwencja rozłącznych skończonych zbiorów. Każdy zestaw jest używany do $reprezentuje$ procesu, a każdy element $-tego$ stan .
• ${\ Displaystyle (o_ {i}) _ {i = 1} ^ {N}}$ (z ${\ Displaystyle o_ {i} \ w S_ {i}}$ ) , sekwencja reprezentująca stan początkowy każdego procesu.
• ${\ Displaystyle (M_ {i, j}) _ {i, j = 1} ^ {N}}$ , skończona sekwencja ${\ Displaystyle N ^ {2 }} rozłączne$$displaystyle$ skończone takie, że każdy zestaw $.$ możliwe komunikaty, które mogą być wysyłane z procesu procesu j $j$ Jeśli ${\ displaystyle i = j}$ , to ${\ displaystyle M_ {i, j}}$ jest pusty.
• ${\ Displaystyle ({\ mathtt {succ}} )_{i=1}^{N}:S_{i}\times \bigcup _{j=1}^{N}\left(M_{j,i}^{[+]}\cup M_{i ,j}^{[-]}\right)\mapsto S_{i}}$ jest ciągiem funkcji przejściowych. Każda funkcja modeluje przejście, jakie można wykonać, emitując lub odbierając dowolny komunikat. W odniesieniu do procesu $którą$$}$ jest do oznaczenia wiadomości, którą można odebrać, i ${$ można wysłać. ja .

Stan globalny

Stan globalny to para gdzie ⟨ $\ Displaystyle \ langle S, C \ rangle}$

• $(s_ {1}, ..., s_ {N})}$ jest uporządkowanym zbiorem stanów, tak że każdy $\ displaystyle s_ { i}}$ reprezentuje stan $-tego$ .
• $C}$$}$$Displaystyle$ jest macierzą taką że każda podciągiem ${\ displaystyle M_ {i, j}}$ .

Początkowy stan globalny to para gdzie ${\ Displaystyle \ langle O \ operatorname {E} \ rangle}$

• $(o_ {1}, ..., o_ {N})}$
• ${E}}$$macierz taka,$ jest zdefiniowana jako ​​dla wszystkich ${\ Displaystyle i, j \ in \ {1, ..., N \}}$${i, j}}$ { równa się pustemu słowu, ${\ Displaystyle \ epsilon}$ .

Krok

Istnieją dwa rodzaje kroków, etapy odbierania wiadomości i etapy wysyłania wiadomości.

Krok, w którym $odbiera$ wiadomość wysłaną wcześniej przez $-ty$ to para postaci ${\ Displaystyle \ lewo \ langle (s_ {1} ,\kropki ,s_{j},\kropki ,s_{n}),\left({\begin{array}{lll}c_{1,1}&\kropki &c_{1,n}\\\kropki & \dots &\dots \\\dots &m_{i,j}c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n }\end{array}}\right)\right\rangle \vdash \left\langle (s_{1},\dots ,s'_{j},\dots ,s_{n}),\left({\ begin{tablica}{ll}c_{1,1}&\kropki &c_{1,n}\\\kropki &\kropki &\kropki \\\kropki &c_{i,j}&\kropki \\\kropki & \dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle }$ kiedy ${\ Displaystyle {\ mathtt {succ}} _ {i} (s_ {j}, + m_ {i, j}) = s '_ {j}},$ z ${\ Displaystyle m'_ {i, j} \ w M_ {i, j}}$ . Podobnie para, w której wiadomość jest wysyłana przez $\ Displaystyle \ lewo \ langle ( s_{1},\kropki ,s_{i},\kropki ,s_{n}),\left({\begin{tablica}{ll}c_{1,1}&\kropki &c_{1,n}\ \\kropki &\kropki &\kropki \\\kropki &c_{i,j}&\kropki \\\kropki &\kropki &\kropki \\c_{n,1}&\kropki &c_{n,n}\ end{array}}\right)\right\rangle \vdash \left\langle (s_{1},\kropki ,s'_{i},\kropki ,s_{n}),\left({\begin{ array}{lll}c_{1,1}&\kropki &c_{1,n}\\\kropki &\kropki &\kropki \\\kropki &m_{i,j}c_{i,j}&\kropki \ \\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle }$$($ do $jest$ parą postaci kiedy ${\ Displaystyle {\ mathtt {succ}} _ {i} (s_ {i}, -m_ {i, j}) = s'_ {i}}$

Uruchomić

Przebieg jest sekwencją stanów globalnych takich, że krok wiąże stan z następnym, oraz że pierwszy stan jest stanem początkowym .

Mówi się, że stan globalny $jest$ jeśli istnieje przechodzący przez ten

Problemy

Wraz z wprowadzeniem samej koncepcji udowodniono, że gdy dwie maszyny o skończonych stanach komunikują się tylko jednym rodzajem komunikatów, można rozstrzygnąć i zidentyfikować ograniczoność, zakleszczenia i nieokreślony stan odbioru, podczas gdy nie ma to miejsca, gdy maszyny komunikują się z dwoma lub więcej rodzajów wiadomości. Później zostało udowodnione, że gdy tylko jedna maszyna skończonych stanów komunikuje się z jednym typem wiadomości, podczas gdy komunikacja jej partnera jest nieograniczona, nadal możemy decydować i identyfikować ograniczenia, zakleszczenia i nieokreślony stan odbioru.

Udowodniono ponadto, że gdy relacja priorytetu komunikatu jest pusta, o ograniczoności, zakleszczeniach i nieokreślonym stanie odbioru można rozstrzygnąć nawet w warunkach, w których w komunikacji między automatami skończonymi występują dwa lub więcej typów komunikatów.

Ograniczenie, zakleszczenia i nieokreślony stan odbioru są rozstrzygalne w czasie wielomianowym (co oznacza, że ​​dany problem można rozwiązać w możliwym do rozwiązania, a nie nieskończonym czasie), ponieważ dotyczące ich problemy decyzyjne są kompletne w niedeterministycznej przestrzeni logarytmicznej.

Rozszerzenia

Niektóre rozważane rozszerzenia to:

• posiadanie zapisu stwierdzającego, że niektóre stany mogą nie otrzymać żadnego komunikatu,
• wiadomości są odbierane w różnych kolejnościach, takich jak FILO,
• niektóre wiadomości mogą zostać utracone,

Układ kanałów

Główny artykuł: system kanałów (informatyka)

System kanałów jest zasadniczo wersją komunikującej się maszyny o skończonych stanach, w której maszyna nie jest podzielona na odrębne procesy. Zatem istnieje jeden stan stanu i nie ma ograniczeń dotyczących tego, który system może odczytywać/zapisywać na dowolnym kanale.

Formalnie, biorąc pod uwagę protokół $\ Displaystyle \ langle (S_{i})_{i=1}^{n},(o_{i})_{i=1}^{n},(M_{i,j})_{i,j=1} ^{n},({\mathtt {succ}})_{i}\rangle }$ , związany z nim system kanałów to ${\ Displaystyle \ langle \ prod (S_ {i}) _ {i = 1} ^ {n}, (o_ {i}) _ {i = 1} ^ {n}, \ bigcup _ {i, j = 1} ^ {n} (M_ {i, j}), \ Delta \ rangle}$$,$ gdzie jest $\ Displaystyle (($ i ${\ Displaystyle ((s_ {1}, \ kropki, s_ {i}, \ kropki, s_ {n}) ,!m_{i,j},(s_{1},\kropki,{\mathtt {succ}}_{i}(s_{i},-m_{i,j}),\kropki,s_{n })}$ .