Membrany ruchome

Systemy błonowe zostały zainspirowane strukturą i funkcjonowaniem żywych komórek. Zostały one wprowadzone i zbadane przez Gh. Pauna pod nazwą systemów P [24] ; niektóre zastosowania układów membranowych przedstawiono w [15] . Systemy membranowe są zasadniczo modelami systemów rozproszonych, równoległych i niedeterministycznych. Tutaj motywujemy i prezentujemy membrany mobilne. Błony ruchome reprezentują wariant systemów błon inspirowanych ruchami biologicznymi wynikającymi z endocytozy i egzocytozy. Mają ekspresyjną moc zarówno systemów P, jak i rachunków procesowych z mobilnością, taką jak mobilne otoczenie [11] i kamieni branowych [10] . Obliczenia z membranami ruchomymi można definiować w określonych konfiguracjach (jak rachunki procesów), podczas gdy reprezentują one również formalizm oparty na regułach (jak systemy P).

Model charakteryzuje się dwiema zasadniczymi cechami:

• Struktura przestrzenna składająca się z hierarchii membran (które nie przecinają się) z obiektami z nimi powiązanymi. Membrana bez żadnych innych membran w środku nazywana jest elementarną.
• Ogólne zasady opisujące ewolucję struktury: endocytoza (przesuwanie błony elementarnej do wnętrza błony sąsiedniej) i egzocytoza (przesuwanie błony elementarnej na zewnątrz błony, w której się znajduje). Bardziej szczegółowe zasady podaje pinocytoza (pochłaniająca zero błon zewnętrznych) i fagocytoza (pochłaniająca tylko jedną zewnętrzną błonę elementarną).

Obliczenia są wykonywane w następujący sposób: zaczynając od początkowej struktury, system ewoluuje, stosując reguły w sposób niedeterministyczny i maksymalnie równoległy. Reguła ma zastosowanie, gdy dostępne są wszystkie przedmiotowe obiekty i membrany pojawiające się po jej lewej stronie. Maksymalnie równoległy sposób korzystania z reguł oznacza, że ​​w każdym kroku stosowany jest maksymalny multizbiór reguł, a mianowicie taki multizbiór reguł, że do zbioru nie można dodać żadnej kolejnej reguły. Konfiguracja zatrzymująca zostaje osiągnięta, gdy nie ma zastosowania żadna reguła. Wynik jest reprezentowany przez liczbę obiektów powiązanych z określoną membraną.

$reguł$ formalizm, który opisuje ruch membran wewnątrz struktury przestrzennej poprzez zastosowanie reguł z danego zestawu . Mobilność zapewnia konsumpcja i przepisywanie obiektów. Pod względem obliczeniowym praca jest wykonywana przy użyciu konfiguracji membranowych. A zestaw konfiguracji membran (w zakresie przez $\ Displaystyle M, N, \ kropki}$$N$ os zdefiniowany za pomocą wolnej monoidy ${\ Displaystyle V ^{*}}$ (w zakresie przez ${\ Displaystyle u, v, \ kropki}$ ) generowany przez skończony alfabet ${\ Displaystyle V}$ (w zakresie przez ${\ Displaystyle a, b, \ kropki}$ ):

${\ Displaystyle \ qquad \ qquad M:: = u \; \ mid \; [\; M \;] _ {u} \; \ mid \; M \|M}$

Jeśli i są to dwie konfiguracje membran, $redukuje$${\ displaystyle M}$$do$ ( oznaczone przez $M \ rightarrow N}$$displaystyle$ ), jeśli istnieje M {\ displaystyle M} i N $displaystyle N}$ w zbiorze reguł mających $,$ do konfiguracji taka że ​​nowa konfiguracja ${\$ jest uzyskiwany. Przy stosowaniu reguł ${\ displaystyle R}$ stosuje się również następujące reguły wnioskowania: R {\ displaystyle R}

${\ Displaystyle \ qquad {\ it {(Comp1)}} \ quad {\ Frac {\ Displaystyle M \ \ rightarrow \ M '} {\ Displaystyle M \ | N \ \ rightarrow \ M' \ | N}}; \ qquad \ qquad {\ it {(Comp2)}} \ quad {\ frac {\ Displaystyle M \ \ rightarrow \ M' \ qquad \ Displaystyle N \ \ rightarrow \ N'} {\ dis styl gry M\|N\ \rightarrow \ M'\|N'}}}$ ;

${\ Displaystyle \ qquad {\ to {(Mem)}} \ {\ Frac {\ Displaystyle M \ \ rightarrow \ M '} {\ Displaystyle [\; M \;] _ {u} \ rightarrow [\; M ' \;] _ {u}}}; \ qquad \ qquad {\ it {(Struc)}} \ {\ Frac {\ Displaystyle M \ equiv _ {mem} M'\ quad M'\ strzałka w prawo N' \ quad \ N '\ równoważnik _ {mem} N} {\ Displaystyle M \ rightarrow N}}}$

Opisując obliczenia systemów membran ruchomych, $.$ jest $początkowa$ i zestaw reguł Reguły zastosowane w tym artykule opisują $}}}$${\ Displaystyle {\ to {endocytoza}}}$ jot mi do t ruch (przesuwanie elementarnej błony wewnątrz sąsiedniej błony), ${\ Displaystyle {\ to {egzocytoza}}}$ ruch (przesuwanie elementarnej membrany membrana na zewnątrz membrany, w której jest umieszczona), $Displaystyle {\ to {pinocytoza}}}$ (pochłaniając zero błon zewnętrznych) i $Displaystyle {\ it {fagocytoza}}}$ (pochłaniając tylko jedną zewnętrzną błonę elementarną).

Moc obliczeniowa membran mobilnych

Specyficzną cechą membran ruchomych jest to, że ten nowy model oparty na regułach jest odpowiedni do udowodnienia obliczalności wyników w kategoriach maszyn Turinga , a nie poprzez redukcję do rachunku lambda, jak w przypadku rachunków procesowych z ruchliwością. W tej sekcji zdefiniowano cztery klasy membran inspirowanych faktami biologicznymi i pokazano, że ich moc obliczeniowa zależy od początkowej konfiguracji i zestawu zastosowanych reguł.

Proste membrany mobilne

Systemy prostych błon ruchomych (SM) są zdefiniowane na podstawie zestawu konfiguracji i ewoluują przy użyciu reguł endocytozy i egzocytozy , a mianowicie przesuwania membrany wewnątrz sąsiedniej błony lub na zewnątrz błony ${\ displaystyle {\ mathcal {M}}}$ odpowiednio, gdzie jest umieszczony. Ewolucja od konfiguracji do innej odbywa się przy użyciu reguł ze zbioru reguł zdefiniowanego w następujący sposób: ${\ displaystyle R}$

${\ Displaystyle [[a \;\|\; M]_ {m} \;\|\;N]_ {k}\rightarrow [[v\;\|\;M]_ {m}\;\|\;N]_{k}}$ dla ${\ Displaystyle k, m \ in {\ mathcal {N}}}$ , ${\ Displaystyle a \ in V}$ , ${\ displaystyle v \ w V ^ {*}}$ ; (lokalna ewolucja obiektu)

$_$ _ ${\ Displaystyle m \ w {\ mathcal {N}}}$ , ${\ Displaystyle a \ w V}$ , ${\ Displaystyle v \ w V ^ {*}}$ ; (globalna ewolucja obiektów)

${\ Displaystyle [a \; \ | \; M_ {1}] _ {h} \; \ | \; [M] _ {m} \ rightarrow [[b \; \|\; M_ {1}] _ {h} \; \|\; M]_ {m}} dla h , m ∈ N {\ Displaystyle h, m \ in {\ mathcal {N}}} za$ , $a$ Displaystyle $}$ ; (endocytoza)

${\ Displaystyle [[a \; \ | \; M_ {1}] _ {h} \; \ | \;M]_{m}\rightarrow [b\;\|\;M_{1}]_{h}\;\|\;[M]_{m}} , dla$ h $\ displaystyle h, m \ in {\ mathcal {N}}}$ , ${\ Displaystyle a, b \ in V}$ ; (egzocytoza)

gdzie ${\ displaystyle M_ {1}}$ to multiset, a ${\ displaystyle M}$ , ${\ displaystyle N}$ to dowolne konfiguracje membranowe.

Kompletność Turinga można uzyskać stosując dziewięć membran wraz z operacjami endocytozy i egzocytozy [21] . W [17] udowodniono, że do uzyskania mocy maszyny Turinga wystarczą cztery ruchome membrany, podczas gdy w [4] liczba membran jest zmniejszona do trzech.

${\ Displaystyle SM (levol, endo, exo)}$ oznacza rodzinę wszystkich zestawów generowanych wewnątrz danej błony przez proste ruchome błony przy użyciu lokalnych reguł ewolucji ( ${\ Displaystyle levol}$ ), zasady endocytozy i egzocytozy. Ilekroć rządzi globalna ewolucja ( ${\ displaystyle gevol}$$\ displaystyle gevol$ , parametr zastąpiony przez $}$ { Jeśli typ reguł nie jest używany, to jego nazwa jest pomijana na liście. Liczba membran nie zwiększa się podczas obliczeń, ale może się zmniejszyć, wysyłając membrany z układu. przypadku ${\ Displaystyle SM_ {n} (gevol, endo, exo)}$ oznacza rodzinę zbiorów wektorów liczb naturalnych obliczonych przy użyciu co najwyżej $ n $ membran. $oznaczał$ obliczalnych zestawów wektorów Turinga generowanych przez dowolne gramatyki

[17] udowodniono , że ${\ Displaystyle SM_ {4} (gevol, endo, exo) = RE}$ . Linia badawcza zapoczątkowana w obliczeniach membranowych polega na znalezieniu systemów membranowych z minimalnym zestawem składników, które są wystarczająco mocne, aby osiągnąć pełną moc maszyn Turinga. W ten sposób poprzedni wynik przedstawiony w [17] są ulepszone poprzez zmniejszenie liczby membran do trzech. Co więcej, osiąga się to poprzez zastosowanie lokalnych reguł ewolucji zamiast globalnych reguł ewolucji.

Twierdzenie. ${\ Displaystyle SM_ {3} (poziom, endo, egzo) = RE}$ .

Dowód tego wyniku wykorzystuje podobną technikę jak w [4] .

Ulepszone membrany mobilne

Układy wzmocnionych błon ruchomych są odmianą prostych układów błon zaproponowanych w [1] do opisu niektórych mechanizmów biologicznych układu odpornościowego. Operacje rządzące ruchliwością systemów wzmocnionych błon ruchomych to endocytoza (endo), egzocytoza (exo), wymuszona endocytoza (fendo), wymuszona egzocytoza (fexo). Ewolucja od konfiguracji do innej odbywa się za pomocą reguł ze zbioru zasady zdefiniowane w następujący sposób: ${\ displaystyle R}$

${\ Displaystyle [u \; \ | \; v \; \ | \; M]_ {h} \; \|\; [v '\;\|\; N]_ {m} \! \ rightarrow \! [w '\; \|\; [w] _ {h }]_{m}}$ dla ${\ Displaystyle h, m \! \ w \! {\ mathcal {N}}; u \! \ w \! V ^ {+}, v, v', w, w'\ !\w \!V^{*}}$ ; (endocytoza)

${\ Displaystyle [v '\;\|\; N \;\|\; [u\;\|\;v\;\|\;M]_{h}]_{m}\!\rightarrow \![w\;\|\;M]_{h}\;\| \;[w'\;\|\;N]_{m}}$ , dla ${\ Displaystyle h, m \! \ w \! \! {\ mathcal {N}}; u \ w V ^ {+}, v, v', w, w'\w V^{*}}$ ; (egzocytoza)

${\ Displaystyle [v \; \|\; M] _ {h} \; \|\;[u\;\|\;v'\;\|\;N]_{m}\!\!\rightarrow \!\![[w\;\|\;M]_{h } \;\|\; w '\;\|\;N]_ {m}}$ dla ${\ Displaystyle h, m \! \! \ w \! \! {\ mathcal {N} }}$ , ${\ Displaystyle u \! \ in \! V ^ {+}, v, v '\!, w, w' \! \ w \! V^{*}}$ ; (wzmocniona endocytoza)

${\ Displaystyle [u \; \|\; v '\;\|\; [v\;\|\;M]_{h}\;\|\;N]_{m}\!\!\rightarrow \!\![w\;\|\;M]_{h} \;\|\;[w'\;\|\;N]_{m}}$ dla ${\ Displaystyle h, m \! \ w \! {\ mathcal {N}}, u \ w V ^ {+}, v, v ', w, w' \w V^{*}}$ ; (wzmocniona egzocytoza)

\ noindent gdzie $jest$ i $jest$ konfiguracją membrany.

Moc obliczeniowa systemów wzmocnionych membran ruchomych wykorzystujących te cztery operacje została zbadana w [20] , gdzie udowodniono, że dwanaście membran może zapewnić uniwersalność obliczeniową, podczas gdy w [4] wynik jest poprawiony poprzez zmniejszenie liczby membran do dziewięciu . Warto zauważyć, że w przeciwieństwie do poprzednich wyników, w żadnym z wyników (i ich dowodach) nie zastosowano przepisywania obiektu za pomocą reguł bezkontekstowych.

Wzajemna zależność między tymi czterema operacjami jest dość potężna, a moc obliczeniowa maszyny Turinga jest uzyskiwana przy użyciu dwunastu membran bez użycia bezkontekstowej ewolucji obiektów [20] .

Rodzina wszystkich zestawów generowanych wewnątrz danej membrany przez ulepszone membrany ruchome stopnia co najwyżej $przy$${ \ Displaystyle \ alfa \ subseteq \ {exo, endo, fendo, fexo \}}$ reguł jest oznaczony przez ${\ Displaystyle EM_ {n} (\ alfa)}$ .

Twierdzenie. ${\ Displaystyle EM_ {3} (endo, egzo) = EM_ {3} (fendo, fekso )}$ .

Twierdzenie. $\ Displaystyle EM_ {12} (endo, egzo, fendo, fekso) = RE}$ .

Dowodząc wyniku poprzedniego twierdzenia, autorzy nie wykorzystali optymalnej konstrukcji układu membranowego. Poniżej zostanie udowodnione, że przy użyciu tych samych reguł ( endo , exo , fendo , fekso ) można zbudować system membranowy, używając tylko dziewięciu membran zamiast dwunastu. Czy jest to optymalna konstrukcja, pozostaje otwartym problemem.

Twierdzenie. $\ Displaystyle EM_ {9} (endo, egzo, fendo, fekso) = RE}$ .

Dowód jest podobny do przedstawionego w [4] .

Wzajemne membrany ruchome

Zgodnie z podejściem przedstawionym w [3] , „układy wzajemnych błon ruchomych” reprezentujące wariant układów prostych błon ruchomych, w których endocytoza i egzocytoza działają zawsze wtedy, gdy zaangażowane błony „zgadzają się” co do ruchu, są określone; ta umowa jest opisana przy użyciu podwójnych obiektów ${\ displaystyle a}$ i ${\ displaystyle {\ overline {a}}}$ w zaangażowanych membranach. Operacjami rządzącymi ruchliwością układów wzajemnych błon ruchomych są wzajemna endocytoza (mutual endo) i wzajemna egzocytoza (mutual exo). Ewolucja od konfiguracji do innej odbywa się przy użyciu reguł ze zbioru reguł zdefiniowanego w następujący sposób: ${\ displaystyle R}$

${\ Displaystyle [u \; \ | \; v \; \ | \;M]_{h}\;\|\;[{\overline {u}}\;\|\;v'\;\|\;N]_{m}\rightarrow [\;[w\ ;\|\;M]_{h}\;\|\;w'\;\|\;N]_{m}}$ dla $, m \ in {\ mathcal {N}}, u, {\ overline {u}} \ w V ^ {+ },v,v',w,w'\!\!\in V^{*}}$ ; (wzajemna endocytoza)

${\ Displaystyle [{\ overline {u}} \;\|\ ;v'\;\|\;N\;\|\;[u\;\|\;v\;\|\;M]_{h}]_{m}\rightarrow [w\;\| \;M]_{h}\;\|\;[w'\;\|\;N]_{m}}$ dla $, m \ in {\ mathcal {N}}, u, {\ overline {u}} \ w V ^ {+ },v,v',w,w'\!\!\in V^{*}}$ ; (wzajemna egzocytoza)

gdzie $jest multiset$ jest $dowolną$ membrany.

Wystarczy wziąć pod uwagę inspirowane biologicznie operacje wzajemnej endocytozy i wzajemnej egzocytozy oraz trzy membrany, aby uzyskać pełną moc obliczeniową maszyny Turinga [6] . Trzy reprezentuje również minimalną liczbę błon, aby właściwie omówić ruch zapewniany przez endocytozę i egzocytozę: praca z konfiguracjami odpowiadającymi systemowi dwóch błon poruszających się wewnątrz błony skórnej.

Rodzina wszystkich zestawów generowanych wewnątrz danej błony przez wzajemne ruchome membrany stopnia $przy$ reguł wzajemnej endocytozy ( mendo ) i reguł wzajemnej egzocytozy ( mexo ) jest oznaczona przez ${\ Displaystyle MM_ {n} (mendo, meksyk)}$ . Dlatego wynik można sformułować w następujący sposób.

Twierdzenie. $\ Displaystyle MM_ {3} (mendo, meksyk) = RE}$ .

W układach prostych membran ruchomych z lokalnymi regułami ewolucji i regułami ruchliwości wiadomo, że układy stopnia trzeciego mają taką samą moc jak maszyna Turinga, natomiast w układach ulepszonych membran ruchomych wykorzystujących tylko reguły ruchliwości stopień układów o takiej samej mocy jak maszyna Turinga wzrasta do dziewięciu. W każdej regule ruchliwości z układów prostych i udoskonalonych membran ruchomych, po lewej stronie reguł pojawia się w dowodach tylko jeden obiekt. Używając multisetów zamiast obiektów i synchronizacji przez obiekty i koobiekty, dowiedziono, że wystarczy wziąć pod uwagę tylko układy trzech wzajemnych błon ruchomych wraz z operacjami wzajemnej endocytozy i wzajemnej egzocytozy, aby uzyskać pełną moc obliczeniową Turinga maszyna.

Dowód prowadzony jest w podobny sposób jak dowód na uniwersalność obliczeniową układów wzmocnionych membran ruchomych [20] .

Wzajemne membrany z obiektami na powierzchni

Układy membranowe [24] i rachunek branowy [10] wychodzą z tych samych obserwacji; są one jednak budowane z myślą o innych celach: systemy membranowe formalnie badają obliczeniową naturę i moc różnych cech membran, podczas gdy rachunek branowy jest w stanie dać wierną i intuicyjną reprezentację rzeczywistości biologicznej. w [12] inicjatorzy tych dwóch formalizmów opisują przyświecające im cele: „Podczas gdy informatyka membranowa jest gałęzią informatyki naturalnej, która próbuje wyabstrahować modele obliczeniowe, w sensie Turinga, ze struktury i funkcjonowania komórki, wykorzystując zwłaszcza automaty, język i narzędzia teorii złożoności, rachunki branowe zwracają większą uwagę na wierność rzeczywistości biologicznej, mają za główny cel biologię systemów i wykorzystują zwłaszcza ramy algebry procesów.

W pracy [2] zdefiniowano układy wzajemnych błon z obiektami na powierzchni, kierując się ideą dodawania obiektów na błonie i wykorzystując inspirowane biologicznie zasady pino/exo/phago pochodzące z [12,14,18,19] . Przedmioty i współobiekty są używane w regułach fago i egzo w celu zilustrowania faktu, że obie zaangażowane membrany zgadzają się co do ruchu. Ewolucja od konfiguracji do innej odbywa się przy użyciu reguł ze zbioru reguł zdefiniowanego w następujący sposób: ${\ displaystyle R}$

${\ Displaystyle [M] _ {v \; \|\; a \; \|\; u} \ rightarrow [[~ ]_{u\;\|\;x}\;\|\;M]_{v\;\|\;y}} ,$ dla ${\ Displaystyle a \ w V, u, v, x, y \ w V ^ {*}, ux, vy \ w V ^ {+}} ($ pino)

${\ Displaystyle [[M] _ {a \;\|\; u} \;\|\;N ]_{{\overline {a}}\;\|\;v}\rightarrow M\;\|\;[N]_{u\;\|\;v\;\|\;x}}$ , dla za ${\ Displaystyle, {\ overline {a}} \ w V, u, v, x \ w V ^ {*}, uvx \ w V ^ {+}} (exo$ )

$\|\;N]_{v\;\|\;y}} , dla$${\ Displaystyle [M_ {1}] _ {a \; \ |\;u}\;\|\;[N]_{{\overline {a}}\;\|\;b\;\|\;v}\rightarrow [[[M_{1}]_{ u\;\|\;x}]_{b}\$ a ${\ Displaystyle a, {\ overline {a}}, b \! \ w \! V, u, v, x, y\in V^{*},ux,vy\in V^{+}}$ (fago)

\noindent gdzie to multiset i $displaystyle$$M}$ , ${\ displaystyle N}$ konfiguracje membran.

Badana jest moc obliczeniowa układów wzajemnych membran z obiektami na powierzchni sterowanymi parami reguł: pino/egzo lub phago/egzo, udowadniając, że są one uniwersalne nawet przy niewielkiej liczbie membran. Przypadki te były już badane w [19] ; jednak lepsze wyniki uzyskuje się przez zwiększenie liczby membran. Podsumowanie wyników (istniejących i nowych) przedstawiono w następujący sposób:

Podsumowanie rezultatów

---

Operacje	${\ displaystyle \ qquad}$ Liczba membran	${\ Displaystyle \ qquad}$ Waga	${\ displaystyle \ qquad}$ RE	${\ Displaystyle \ qquad}$ Gdzie
Pino, eks	8	4,3	Tak	Twierdzenie 6.1 [19]
Pino, eks	3	5,4	Tak	Tutaj
Phago, eks	9	5,2	Tak	Twierdzenie 6.2 [19]
Phago, eks	9	4,3	Tak	Twierdzenie 6.2 [19]
Phago, eks	4	6,3	Tak	Tutaj

W wyniku obliczeń uwzględniany jest wektor krotności multisetu ze wszystkich membran. Tak więc wynik obliczenia zatrzymania składa się ze wszystkich wektorów opisujących wielość obiektów ze wszystkich membran; nieprzerwane obliczenia nie dają żadnych danych wyjściowych. Liczba obiektów z prawej strony reguły nazywana jest jej wagą . Rodzina wszystkich zestawów generowanych przez układy wzajemnych membran z obiektami na powierzchni wykorzystującymi w dowolnym momencie podczas zatrzymywania obliczeń co najwyżej $membrany$ dowolną z reguł ${\ Displaystyle r_ {1}, r_ {2} \ w \ {pino, exo, phago \}}$ wagi najwyżej ${\ odpowiednio displaystyle r, s}$ jest oznaczony przez ${\ Displaystyle MMOS_ {n} (r_ {1} (r), r_ {2} (s) }$ ). Gdy jeden z parametrów nie jest ograniczony, jest zastępowany przez ${\ displaystyle *}$ .

[19] udowodniono , że układy ośmiu membran z obiektami na powierzchni i wykorzystujące operacje pino i egzo o wadze czwartej i trzeciej są uniwersalne. Liczbę membran można zmniejszyć z ośmiu do trzech. Jednak aby to zrobić zwiększa się wagę operacji pino i exo o jeden, a mianowicie z cztery i trzy do pięciu i czterech. Oznacza to, że aby zbudować uniwersalny system membran ruchomych z obiektami na powierzchni za pomocą operacji pino i egzo, należy zdecydować, czy chce się zminimalizować liczbę membran, czy wagi operacji.

Twierdzenie. ${\ Displaystyle MMOS_ {m} (pino (r), exo (s)) = RE}$ dla wszystkich ${\ Displaystyle m \ geq 3, r \ geq 5, s \ geq 4}$ .

[19] udowodniono , że układy dziewięciu membran z obiektami na powierzchni i wykorzystujące operacje fago i egzo o wadze cztery i trzy (lub pięć i dwa) są uniwersalne. Liczbę membran można zmniejszyć z dziewięciu do czterech, ale w tym celu zwiększa się wagę operacji fago i egzo z czterech i trzech (lub pięciu i dwóch) do sześciu i trzech. Podczas konstruowania kompletnego systemu Turinga z ruchomymi membranami z obiektami na powierzchni za pomocą operacji fago i egzo, pojawia się ten sam problem, co przy użyciu operacji pino i egzo: a mianowicie, aby wybrać albo minimalizację liczby membran, albo wagi operacji.

Twierdzenie. ${\ Displaystyle MMOS_ {m} (phago (r), exo (s)) = RE}$ dla wszystkich ${\ Displaystyle m \ geq 4, r \ geq 6, s \ geq 3}$ .

Ekspresyjna moc membran mobilnych

W dalszej części pokazano, że ruchome membrany mają co najmniej moc ekspresyjną ruchomych otoczenia i kamieni branowych poprzez kodowanie ruchomych otoczenia i kamieni branowych w niektórych systemach ruchomych membran.

Osadzanie otoczenia mobilnego w membranach mobilnych

Mobilne membrany i mobilne otoczenia [11] mają podobne struktury i wspólne koncepcje. Oba mają hierarchiczną strukturę reprezentującą lokalizacje, mają na celu opisanie mobilności i są wykorzystywane do opisu różnych zjawisk biologicznych [10,15] . Ambienty mobilne są odpowiednie do reprezentowania ruchu ambientów przez ambienty i komunikacji, która odbywa się wewnątrz granic ambientów. Systemy membranowe są odpowiednie do przedstawiania ewolucji obiektów i ruchu obiektów i membran przez membrany. Porównanie tych nowych modeli ( mobile ambients i ruchome membrany) oraz kodowanie otoczenia na membrany. To osadzanie jest zasadniczo przedstawione w [5] .

Bezpieczne ambienty to odmiana ambientów mobilnych , w której jakikolwiek ruch ambientu odbywa się tylko za zgodą obu uczestników. Mobilność jest zapewniana przez konsumpcję pewnych par zdolności. Bezpieczne otoczenie różni się od otoczenia mobilnego dodatkowymi koakcjami: jeśli w mobilnym otoczeniu ruch jest inicjowany tylko przez poruszające się otoczenie, a docelowe otoczenie nie ma nad nim kontroli, w bezpiecznym otoczeniu obaj uczestnicy muszą wyrazić zgodę, używając dopasowania między działanie i współdziałanie. Poniżej podano krótki opis czystych bezpiecznych warunków otoczenia (SA); więcej informacji można znaleźć w [22,23] . Biorąc pod uwagę nieskończony zestaw nazw (w zakresie przez $)$${\ Displaystyle m, n, \ kropki}$ , zestaw procesów SA (oznaczony przez $', B, B', \ kropki} N {\ Displaystyle {\ mathcal {N}}} )$$z$ możliwościami (oznaczonymi przez ${\ Displaystyle C, C ', \ kropki}$ ) są zdefiniowane w następujący sposób:

${\ Displaystyle \ qquad C :: = w \ n \; \mid \;{\overline {wejście}}\ n\;\mid \;out\ n\;\mid \;{\overline {out}}\ n\;\mid \;open\ n\;\mid \;{\overline {otwórz}}\ n}$

${\ Displaystyle \ qquad A:: = 0 \ quad \ mid \ quad A \; \ mid \; B \ quad \ mid \ quad CA \ quad \ mid \ quad n [\; A \; ]}$

Process ${\ displaystyle 0}$ to nieaktywne środowisko mobilne. Ruch ${\ displaystyle C. \, A}$ jest zapewniana przez możliwość , po której następuje wykonanie $}$$displaystyle$ . Otoczenie reprezentuje ograniczone miejsce oznaczone przez $n [\; A \;]},$$Displaystyle$$w$ wykonywany jest proces SA ${\ Displaystyle A \, \ mid \, B}$ to równoległa kompozycja mobilnych środowisk $Displaystyle$ i $B}$ . ${\ Displaystyle (\ nu n) A}$ tworzy nową unikalną nazwę $displaystyle$ zakresie $A}$ . Kongruencja strukturalna $jest$ najmniejszą kongruencją taką ${\ Displaystyle ({\ mathcal {A}}, \ mid, 0)}$ jest monoidem przemiennym.

$reguł$ otoczenia jest zdefiniowana w kategoriach relacji redukcji pomocą następujących aksjomatów

Aksjomaty:

${\ Displaystyle (w) \ quad n [\; w \ mA \ mid A '\;] \ mid m [\; {\ overline {in}} \ mB \ mid B' \;] \ Rightarrow _ {amb} m[\;n[\;A\mid A'\;]\mid B\mid B'\;]}$ ;

${\ Displaystyle (Out) \ quad m [\; n [\; out \ mA \ mid A '\;] \ mid {\ overline {out}} \ mB \ mid B' \;] \ Rightarrow _ {amb} n [\; A \ mid A' \;] \ mid m [\; B \ mid B' \;]}$ ;

${\ Displaystyle (otwarty) \ quad otwarty \ nA \; \ środkowy \; n [\; {\ overline {otwarty}} \ nB \ środkowy B '\ ;]\Strzałka w prawo _{amb}A\;\mid \;B\;\mid \;B'}$ .

Zasady:

${\ Displaystyle (Comp1) \ quad {\ Frac {\ Displaystyle A \ Rightarrow _ {amb} A'} {\ Displaystyle A \; \ mid \; B \ Rightarrow _ {amb} A '\ ;\ mid \; B}};\ qquad \ qquad \ qquad \ qquad (Comp2) \ quad {\ Frac {\ Displaystyle A \ Strzałka w prawo _ {amb} A '\ quad \ Displaystyle B \ Strzałka w prawo _ {amb} B' {\ Displaystyle A \; \ mid \; B \ Rightarrow _ {amb} A' \; \ mid \; B'}}}$ ;

${\ Displaystyle (Amb) \ quad {\ Frac {\ Displaystyle A \ Strzałka w prawo _ {amb} A'} {\ Displaystyle n [\; A \;] \ Strzałka w prawo _ {amb} n [\; A '\;]}};\ qquad \ qquad \ qquad \ qquad (Struc) \ quad {\ Frac {\ Displaystyle A \ równoważnik A', \ A' \ Strzałka w prawo _ {amb} B', \ B'\ równoważnik B {\ Displaystyle A \ Strzałka w prawo _ {amb} B}}}$ .

${\ Displaystyle \ Rightarrow _ {amb} ^ {*}}$ oznacza zwrotne i przechodnie zamknięcie relacji binarnej $amb}}$ .

Tłumaczenie ze zbioru ${$ warunków otoczenia na zbiór konfiguracji membran jest podane formalnie w następujący sposób: $\ displaystyle {\ mathcal {A}}}$

Definicja. ${T}}: {\ mathcal {A}} \ rightarrow {\ mathcal {M}}}$ ZA ${\ Displaystyle {\ mathcal {T}} (A) = dlock ~ {\ mathcal {T}} _ {1} (A)} T$ jest podane przez $\ mathcal {T }}_{1}:{\mathcal {A}}\rightarrow {\mathcal {M}}}$ \ jest

${\ Displaystyle \ qquad {\ mathcal {T}} _ {1} (A) =}$${\ Displaystyle {\ rozpocząć {przypadki} cap ~ n \; \|\; [~] _ {cap ~ n} & {\ mbox {if}} A = czapka ~ n \\ czapka ~ n \; \ | \;[\;{\mathcal {T}}_{1}(A_{1})\;]_{cap~n}&{\mbox{if}}A=cap~n.\,A_{1 }\\\;[\;{\mathcal {T}}_{1}(A_{1})\;]_{n}&{\mbox{if}}A=n[\;A_{1} \;]\\\;[~]_{n}&{\mbox{if}}A=n[~]\\{\mathcal {T}}_{1}(A_{1})\;\ |\;{\mathcal {T}}_{1}(A_{2})&{\mbox{if }}A=A_{1}\,\mid \,A_{2}\\\lambda &{ \mbox{if }}A=0\end{przypadki}}}$

Obiekt jest $struktury$ , aby zapobiec zużyciu obiektów zdolności w systemie membranowym, który odpowiada mobilnemu otoczeniu, które nie może dalej

Propozycja. Strukturalnie spójne otoczenia są tłumaczone na strukturalnie spójne systemy membranowe; co więcej, strukturalnie przystające translowane systemy membranowe odpowiadają strukturalnie przystającym otoczeniem: ${\ Displaystyle \ qquad \ qquad A \ equiv _ {amb} B}$ iff ${\ displaystyle {\ mathcal {T}} (A) \ równoważnik _ {mem} {\ mathcal {T}} (B)}$ .

Biorąc pod uwagę dwa systemy membranowe i ${\ Displaystyle$$N}$ z tylko jednym obiektem $\ displaystyle dlock}$ , $mem} N}$ jeśli istnieje sekwencja reguł z określonego zestawu reguł używanych w [7] ${\ displaystyle r_ {1}, \ ldots, r_ {i}}$ , tak że stosując reguły z tego zestawu do konfiguracji $membrany$ się $konfigurację$ .

Propozycja. Jeśli $Displaystyle$ są dwoma otoczeniami, a M $jest$$M}$ systemem membranowym takim, że $Rightarrow _ {amb} B}$ i ${\ Displaystyle M = {\ mathcal {T}} (A)}$ , to istnieje zestaw reguł mających zastosowanie do ${\ Displaystyle M}$ taki, że ${\ Displaystyle M \ Strzałka w prawo _ {mem} N}$ i ${\ Displaystyle N = {\ mathcal {T}} (B)}$ .

Propozycja. Niech i będą dwoma systemami ${\$${\ Displaystyle M = {\ mathcal {T}} (A)}$ tylko jednym $displaystyle$ takim, że $displaystyle$$} i N {\$ . Jeśli istnieje zestaw reguł mających zastosowanie do $takich$ że ${\ Displaystyle M \ Rightarrow _ {mem} N}$ wtedy istnieje otoczenie ${\ Displaystyle B}$ z ${\ Displaystyle A \ Rightarrow _ {amb} ^ {*} B}$ i ${\ Displaystyle N = {\ mathcal {T}} (B)}$ . Liczba par obiektów niebędących gwiazdami zużywanych w systemach membranowych jest równa liczbie par zdolności zużywanych w otoczeniu.

Twierdzenie. (Korespondencja operacyjna)

• ZA ${\ Displaystyle A \ Strzałka w prawo _ {amb} B}$ , to $prawo _ { mem}{\mathcal {T}}(B)}$ .
• T ${\ Displaystyle {\ mathcal {T}} (A) \ Rightarrow _ {mem} M}$ , to istnieje ${\ displaystyle B}$ takie, że $\ displaystyle A \ Strzałka w prawo _ {amb} B}$ i ${\ Displaystyle M = {\ mathcal {T}} (B)}$ .

Osadzanie rachunku Brane'a w ruchomych membranach

Rozważany jest fragment rachunku branowego zwany PEP oraz wzajemne membrany ruchome z obiektami na powierzchni jako wariant układów z membranami ruchomymi. Ruchome membrany z obiektami na powierzchni są inspirowane modelem układu membranowego wprowadzonego w [12] z obiektami przyczepionymi do membran. Przedstawiono symulację fragmentu PEP rachunku branowego za pomocą wzajemnych membran z obiektami na powierzchni. Podejście to jest powiązane z innymi pracami próbującymi wykazać związek między układami membranowymi a rachunkiem branowym [8,9,14,18,19] .

Jak to wyrażono w [24] , „na pierwszy rzut oka rola obiektów umieszczonych na membranach jest inna w systemach membranowych i branowych: w obliczeniach membranowych nacisk kładziony jest na ewolucję samych obiektów, podczas gdy w rachunkach branowych obiekty („ białka”) kontrolują głównie ewolucję błon”. Definiując kodowanie fragmentu PEP rachunku branowego we wzajemnych błonach z obiektami na powierzchni, pokazano, że różnica między tymi dwoma modelami nie jest znacząca. Inną różnicę dotyczącą semantyki obu formalizmów wyraża [8] : „podczas gdy rachunki branowe są zwykle wyposażone w przeplataną, sekwencyjną semantykę (każdy krok obliczeniowy składa się z wykonania pojedynczej instrukcji), zwykła semantyka w obliczeniach membranowych jest oparta na maksymalnej równoległości (krok obliczeniowy składa się z maksymalnego zestawu niezależne interakcje)”.

Brane calculus [10] zajmuje się membranami reprezentującymi miejsca aktywności; w ten sposób obliczenia odbywają się na powierzchni membrany. Operacje dwóch podstawowych płytek branowych, pino, exo, phago (PEP) i mate, drip, bud (MBD), są bezpośrednio inspirowane procesami biologicznymi, takimi jak endocytoza, egzocytoza i mitoza. Te ostatnie operacje można symulować za pomocą tych pierwszych [10] .

Rachunek Pino/Exo/Phage - jego składnia

---

Systemy	${\ Displaystyle P, Q}$	${\ Displaystyle :: \, =}$	${\ Displaystyle P \ circ Q \; \ środkowy \; \ sigma (~) \; \ środkowy \; \ sigma (P)}$	gniazda błon
Branes	${\ Displaystyle \ sigma, \ tau}$	${\ Displaystyle :: \, =}$	${\ Displaystyle O \; \ środkowa \; \ sigma \ środkowa \ tau \; \ środkowa \; a. \ sigma}$	kombinacje działań
działania	${\ displaystyle a, b}$	${\ Displaystyle :: \, =}$	${\ Displaystyle n ^ {\ searrow} \; \ środkowy \; {\ overline {n}} ^ {\ searrow }(\sigma )\;\mid \;n^{\nwarrow }\;\mid \;{\overline {n}}^{\nwarrow }\;\mid \;pino(\sigma )}$	phago ${\ Displaystyle \ searrow}$ , exo ${\ Displaystyle \ nwarrow}$

$displaystyle s = s_ {1} \; \ mid \; s_ {2}$ utworzone z łat, gdzie łatka może składać się z innych łatek $=$ } Elementarna łatka $łatka$ się z akcji , po $kolejna$ po jej zużyciu następuje ${\ displaystyle s_ {1} s = a.s_ {1}}$ . Działania często występują w uzupełniających się parach, które powodują interakcję między membranami. Nazwy $służą$ do łączenia w pary działań i kooperacji Cardelli motywuje, że operator replikacji jest używany do modelowania pojęcia „mnóstwa” składników tego samego rodzaju, co jest w rzeczywistości standardową sytuacją w biologii [10] . Operator replikatora nie jest używany, ponieważ systemu membranowego nie można zdefiniować bez dokładnej znajomości początkowej struktury membranowej. ${\ Displaystyle {\ mathcal {P}}}$ oznacza zestaw układów bran zdefiniowanych powyżej. Można wprowadzić pewne skróty: $\ Displaystyle$ za { $a}$ , ${\ Displaystyle 0 (P)}$ jako $\ Displaystyle (P)$ i ${\ Displaystyle 0 (~)}$ jak ${\ Displaystyle (~)}$ .

Relacja kongruencji strukturalnej jest sposobem na przeorganizowanie systemu w taki sposób, że oddziałujące ze sobą części łączą się, jak pokazano na poniższym rysunku:

Pino/Exo/Phage Calculus - kongruencja strukturalna

---

${\ Displaystyle P \ circ Q \ równoważnik _ {b} Q \ circ P}$	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle \ sigma \; \ środkowy \; \ tau \ równoważnik _ {b} \ tau \; \ środkowy \; \ sigma}$
${\ Displaystyle P \ circ (Q \ circ R) \ równoważnik _ {b} (P \ circ Q) \ circ R}$	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle \ sigma \; \ mid \; (\ tau \; \ mid \; \ rho) \ równoważnik _ {b} (\ sigma \; \ mid \; \ tau) \; \ mid \; \ rho}$
${\ Displaystyle \ qquad}$	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle \ sigma \; \ środkowy \; 0 \ równoważnik _ {b} \ sigma}$
${\ Displaystyle \ qquad}$	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle \ qquad}$
${\ Displaystyle P \ równoważnik _ {b} Q {\ mbox {implikuje}} P \ circ R \ równoważnik _ {b} Q \ circ R}$	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle \ sigma \ równoważnik _ {b} \ tau {\ mbox {implikuje}} \ sigma \; \ środkowy \; \ rho \ równoważnik _ {b} \ tau \;\mid \;\rho }$
${\ Displaystyle P \ równoważnik _ {b} Q {\ mbox {i}} \ sigma \ równoważnik _ {b} \ tau {\ mbox {implikuje }} \ sigma (P) \ równoważnik _ {b} \ tau (Q)}$	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle \ sigma \ równoważnik _ {b} \ tau {\ mbox {implikuje}} a. \ sigma \ równoważnik _ {b} a. \ tau}$

Poniżej przedstawiono redukujące reguły rachunku różniczkowego:

Rachunek Pino/Exo/Phago - Reguły redukcji

---

${\ Displaystyle pino (\ rho). \ sigma \ mid \ sigma _ {0} (P) \ rightarrow _ {b} \ sigma \ mid \sigma _{0}(\rho (~)\circ P)}$	${\ Displaystyle \ qquad \ qquad}$	(pino)
${\ Displaystyle {\ overline {n}} ^ {\ nwarrow}. \ tau \ mid \tau _{0}(n^{\nwarrow }.\sigma \mid \sigma _{0}(P)\circ Q)\rightarrow _{b}P\circ \sigma \mid \sigma _{0} \mid \tau \mid \tau _{0}(Q)}$	${\ Displaystyle \ qquad \ qquad}$	(egzo)
${\ Displaystyle n ^ {\ searrow}. \ sigma \ mid \ sigma _ {0} (P) \ circ {\ overline {n}} ^ {\ searrow} (\ rho). \ tau \ mid \ tau _ { 0}(Q)\rightarrow _{b}\tau \mid \tau _{0}(\rho (\sigma \mid \sigma _{0}(P))\circ Q)}$	${\ Displaystyle \ qquad \ qquad}$	(Fago)
${\ Displaystyle P \ rightarrow _ {b} Q {\ mbox {implikuje}} P \ circ R \ rightarrow _ {b} Q \ circ R}$	${\ Displaystyle \ qquad \ qquad}$	(Par)
${\ Displaystyle P \ rightarrow _ {b} Q {\ mbox {implikuje}} \ sigma (P) \ rightarrow _ {b} \ sigma (Q)}$	${\ Displaystyle \ qquad \ qquad}$	(Brane)
${\ Displaystyle P \ równoważnik _ {b} P '{\ mbox {i}} P' \ rightarrow _ {b} Q'{\mbox{i }}Q'\equiv _{b}Q{\mbox{implikuje }}P\rightarrow _{b}Q}$	${\ Displaystyle \ qquad \ qquad}$	(Struktura)

Działanie ${\ displaystyle pino (\ rho)}$ tworzy pustą bańkę w błonie, w której znajduje się działanie ${\ displaystyle pino}$ ; wyobraź sobie, że oryginalna membrana wygina się do wewnątrz i odrywa. Łatka $bańce$ jest parametrem $displaystyle pino}$ . Akcja exo ${\ Displaystyle n ^ {\ nwarrow}}$$punkcie$ współpracą , modeluje łączenie dwóch zagnieżdżonych membran, które rozpoczyna się od stykania się membran w jednym $)$ podsystem zostaje wydalony na zewnątrz, a wszystkie pozostałe płaty dwóch membran stają się ciągłe Akcja phago $,$ ma również komplementarną ${\ Displaystyle {\ overline {n}} ^ {\ searrow} (\ rho)}$$}$ membranę (tę z ) „zjadając” inną membranę (tę z $}$${\ displaystyle P$ ). Ponownie, proces musi być płynny i ciągły, więc jest biologicznie wykonalny. Przechodzi przez membranę owijającą się wokół $displaystyle$$P}$ membranę i łącząc się po drugiej stronie. W związku z tym wokół zjedzonej błony tworzona jest dodatkowa warstwa błony: łatka na tej błonie jest określona parametrem $kofago$ (podobnie jak parametr działania pino).

Tłumaczenie ze zbioru procesów branowych na zbiór konfiguracji membranowych jest podane formalnie w następujący sposób: $P} }}$$displaystyle {\ mathcal {$

Definicja Tłumaczenie jest podane przez ${\ Displaystyle {\ mathcal {T}}: {\ mathcal {P}} \ rightarrow {\ mathcal {M}}}$

${\ Displaystyle {\ mathcal {T}} (P) =}$${\ Displaystyle {\ rozpocząć {przypadki} \; [~] _ {{\ mathcal {S}} (\ sigma)} & {\ mbox {if}} P = \ sigma (~) \\\; [{ \mathcal {T}}(R)]_{{\mathcal {S}}(\sigma )}&{\mbox{if }}P=\sigma (R)\\{\mathcal {T}}(Q )\;\|\;{\mathcal {T}}(R)&{\mbox{if}}P=Q\,\mid \,R\\\end{przypadki}}}$

gdzie ${\ Displaystyle {\ mathcal {S}}: {\ mathcal {P}} \ rightarrow V ^ {*}}$ jest zdefiniowany jako:

${\ Displaystyle {\ mathcal {S}} (\ sigma) =}$${\ Displaystyle {\ rozpocząć {przypadki} \ sigma & {\ mbox {jeśli}} \ sigma = n ^ {\ searrow} lub \ sigma = n ^ {\ nwarrow} lub \ sigma = {\ overline {n}} ^ {\nwarrow }\\{\overline {n}}^{\searrow }\;\|\;S(\rho )&{\mbox{if }}\sigma ={\overline {n}}^{\ searrow }(\rho )\\pino\;\|\;S(\rho )&{\mbox{if }}\sigma =pino(\rho )\\{\mathcal {S}}(a)\; \|\;{\mathcal {S}}(\rho )&{\mbox{if }}\sigma =a.\rho \\{\mathcal {S}}(\tau )\;\|\;{ \mathcal {S}}(\rho )&{\mbox{if }}\sigma =\tau \,\mid \,\rho \\\lambda &{\mbox{if }}\sigma =0\end{ sprawy}}}$

Poniżej przedstawiono zasady działania układów wzajemnych membran z obiektami na powierzchni (MMOS).

Zasady Pino/Exo/Phago w MMOS

---

pino	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle [M] _ {S (pino (\ rho). \sigma \mid \sigma _{0})}\rightarrow [[~]_{S(\rho )}\;\|\;M]_{S(\sigma \mid \sigma _{0})} }$
egzo	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle [[M] _ {S (n ^ {\ nwarrow}. \ sigma \ mid \ sigma _ {0})} \; \ | \; N] _ {S ({\ overline {n}} ^ {\nwarrow }.\tau \mid \tau _{0})}\rightarrow M\;\|\;[N]_{S(\sigma \mid \sigma _{0}\mid \tau \mid \ tau _{0})}}$
Fago	${\ Displaystyle \ qquad \ qquad}$	${\ Displaystyle [M_ {1}] _ {S (n ^ {\ searrow}. \ sigma \ mid \ sigma _ {0})} \; \|\; [N] _ {S ({\ overline {n}} ^ {\ searrow} (\ rho). \ tau \ mid \ tau _ {0})} \ rightarrow [[[M_ {1}] _ {S (\ si gma \mid \sigma _{0})}]_{S(\rho )}\;\|\;N]_{S(\tau \mid \tau _{0})}}$

gdzie jest multiset i $M$$}$ , $displaystyle N}$ to dowolne konfiguracje membranowe.

Kolejny wynik mówi, że dwa systemy PEP, które są strukturalnie równoważne, są przekształcane w układy wzajemnych membran z obiektami na powierzchni, które są strukturalnie równoważne.

Propozycja. Jeśli $jest$ systemem PEP i systemem wzajemnych membran z obiektami na powierzchni, to istnieje ${\ Displaystyle M = {\ mathcal {T}} (P$$} \ Displaystyle N}$ takie, że ${\ Displaystyle M \ równoważnik _ {m} N}$ i ${\ Displaystyle N = {\ mathcal {T}} (Q)}$ , ilekroć ${\ Displaystyle P \ równoważnik _ {b} Q}$ .

Propozycja. Jeśli $\$ systemem PEP i $displaystyle$ systemem wzajemnych membran z obiektami na powierzchni $to$$\ Displaystyle Q}$ takie, że ${\ Displaystyle N = {\ mathcal {T}} (Q)}$ ilekroć ${\ Displaystyle M \ equiv _ {m} N}$ .

Uwaga. W ostatnim twierdzeniu możliwe jest, że ${\ Displaystyle P \ not \ equiv _ {b} Q}$ . Załóżmy, że ${\ Displaystyle P = n ^ {\ searrow}. n ^ {\ nwarrow} (~)}$ . Z translacji wynika, że ${\ Displaystyle M = {\ mathcal {T}} = [~] _ {n ^ {\ searrow} \; \|\; n ^ {\ nwarrow}} \ równoważnik _ {m} [~] _ {n ^{\nwarrow }\;\|\;n^{\searrow }}=N}$ . Możliwe jest, aby ${\ Displaystyle Q = n ^ {\ n warrow}. n ^ {\ searrow} (~)}$ lub ${\ Displaystyle Q = n ^ {\ nwarrow} \ mid n ^{\searrow }(~)}$ takie, że ${\ Displaystyle N = {\ mathcal {T}} (Q)}$ , ale ${\ Displaystyle P \ nie \ equiv _ {b} Q}$ .

Propozycja. Jeśli $jest$ systemem PEP i systemem wzajemnych membran z obiektami na powierzchni, to istnieje ${\ Displaystyle M = {\ mathcal {T}} (P$$} \ Displaystyle N}$ takie, że ${\ Displaystyle M \ rightarrow N}$ i ${\ Displaystyle N = {\ mathcal {T}} (Q)}$ , ilekroć ${\ Displaystyle P \ rightarrow _ {b} Q}$ .

Propozycja. Jeśli $\$ systemem PEP i $displaystyle$ systemem wzajemnych membran z obiektami na powierzchni $to$$\ Displaystyle Q}$ takie, że ${\ Displaystyle N = {\ mathcal {T}} (Q)}$ ilekroć ${\ Displaystyle M \ rightarrow N}$ .

Poniższa uwaga jest konsekwencją faktu, że formalizm wykorzystujący semantykę przeplatania przekłada się na formalizm działający równolegle.

Uwaga. Ostatnia propozycja pozwala ${\ Displaystyle P \ nie \ rightarrow _ {b} Q}$ . Załóżmy, że ${\ Displaystyle P = {\ overline {n}} ^ {\ nwarrow}. {\ overline {n}} ^ {\ nwarrow} (n ^ {\ nwarrow}. n^{\searrow}(~))}$ . Poprzez translację uzyskuje się, że ${\ Displaystyle M = ((~) _ {n ^ {\ nwarrow} \;\|\; n ^ {\ searrow}}) _ {{\ overline {n}} ^ {\ nwarrow} \;\|\;{\ overline {n}} ^{\nwarrow}}}$ , tak że ${\ Displaystyle M \ rightarrow [~] _ {n ^{\searrow}\;\|\;{\overline {n}}^{\nwarrow}}}$ . Można zauważyć, że istnieje ${\ Displaystyle Q = n ^ {\ searrow}. {\ overline {n}} ^ {\ nwarrow} (~)}$ takie, że ${\ Displaystyle N = {\ mathcal {T}} (Q )}$ , ale ${\ Displaystyle P \ nie \ rightarrow _ {b} Q}$ .

Wyniki te przedstawiono wraz z ich dowodami w [2] .

1. B. Aman, G. Ciobanu. Opisywanie układu odpornościowego za pomocą ulepszonych błon komórkowych. elektr. Uwagi z informatyki teoretycznej , tom 194 (3), 5-18, 2008.
2. B. Aman, G. Ciobanu. Systemy membranowe z obiektami powierzchniowymi. proc. Międzynarodowych Warsztatów Komputerowych z Biomolekułami (CBM 2008) , 17—29, 2008.
3. B. Aman, G. Ciobanu. Konkurencja zasobów i synchronizacja w membranach. Proceedings of SYNASC08 , IEEE Computing Society, 145-151, 2009.
4. B. Aman, G. Ciobanu. Proste, ulepszone i wzajemne membrany ruchome. Transactions on Computational Systems Biology XI”, LNBI vol.5750, 26-44, 2009.
5. B. Aman, G. Ciobanu. Przełożenie środowiska mobilnego na systemy P. elektr. Uwagi z informatyki teoretycznej , tom 171 (2), 11-23, 2007.
6. B. Aman, G. Ciobanu. Kompletność Turinga przy użyciu trzech membran ruchomych. Notatki z wykładów z informatyki , tom 5715, 42–55, 2009.
7. B. Aman, G. Ciobanu. O związku między membranami a otoczeniem. Biosystems , tom 91(3), 515-530, 2008.
8. N. Busi. O mocy obliczeniowej rachunku Mate / Bud / Drip Brane: przeplatanie a maksymalna równoległość . Notatki z wykładów z informatyki , tom 3850, Springer, 144-158, 2006.
9. N. Busi, R. Gorrieri. O mocy obliczeniowej rachunku Brane'a. Trzecie warsztaty na temat metod obliczeniowych w biologii systemowej , 106-117, 2005.
10. L. Cardelli. Brane Calculi. Oddziaływania błon biologicznych. Lecture Notes in BioInformatics , tom 3082, 257-278, Springer, 2004.
11. L. Cardelli, A. Gordon. Ambienty mobilne. Notatki z wykładów z informatyki , tom 1378, Springer, 140-155, 1998.
12. L. Cardelli, Gh. Paun. Wynik uniwersalności dla rachunku (membranowego) opartego na operacjach łączenia/kroplowania. Stażysta. J. Podstawy informatyki , tom 17(1), 49-68, 2006.
13. L. Cardelli, S. Pradalier. Gdzie membrany spotykają kompleksy. BioConcur , 2005.
14. M. Cavaliere, S. Sedwards. Systemy membranowe z białkami obwodowymi: transport i ewolucja. elektr. Notatki z informatyki teoretycznej , tom 171 (2), 37-53, 2007.
15. G. Ciobanu, Gh. Păun, MJ Pérez-Jiménez. Zastosowanie obliczeń membranowych . Springera, 2006.
16. J. Dassow, Gh. Paun. Regulowane przepisywanie w teorii języka formalnego . Springer-Verlag, 1990.
17. SN Kryszna. Siła mobilności: wystarczą cztery membrany. Notatki z wykładów z informatyki , tom 3526, 242–251, Springer, 2005.
18. SN Kryszna. Obliczenia membranowe z transportem i osadzonymi białkami. Informatyka teoretyczna , tom 410, 355-375, 2009.
19. SN Kryszna. Wyniki uniwersalności dla systemów P oparte na operacjach rachunku branowego. Informatyka teoretyczna , tom 371, 83-105, 2007.
20. SN Kryszna, G. Ciobanu. O mocy obliczeniowej ulepszonych membran mobilnych. Notatki z wykładów z informatyki , tom 5028, 326-335, 2008.
21. SN Kryszna, Gh. Paun. Systemy P z membranami mobilnymi. Natural Computing , tom 4 (3), 255-274, 2005.
22. F. Levi, D. Sangiorgi. Kontrolowanie zakłóceń w otoczeniu. Postępowanie POPL'00 , ACM Press, 352-364, 2000.
23. F. Levi, D. Sangiorgi. Mobilne bezpieczne otoczenie. ACM TOPLAS , tom 25, 1-69, 2003.
24. Gh. Paun. Obliczenia membranowe. Wstęp. Springer-Verlang, Berlin, 2002.
25. Gh. Paun. Obliczenia membranowe i Brane Calculi (niektóre notatki osobiste). elektr. Uwagi z informatyki teoretycznej , tom 171, 3-10, 2007.