Мобильные мембраны

Мембранные системы были созданы на основе структуры и функционирования живых клеток. Они были введены и изучены Г.Пауном под названием П-систем [24] ; некоторые применения мембранных систем представлены в [15] . Мембранные системы по сути являются моделями распределенных, параллельных и недетерминированных систем. Здесь мы мотивируем и представляем мобильные мембраны . Мобильные мембраны представляют собой вариант мембранных систем, основанных на биологических движениях, обусловленных эндоцитозом и экзоцитозом. Они обладают выразительной силой как P-систем, так и подвижных исчислений процессов, таких как мобильные эмбиенты [11] и исчисления на бранах [10] . Вычисления с мобильными мембранами могут быть определены для конкретных конфигураций (например, исчисление процессов), а также представляют собой формализм, основанный на правилах (например, P-системы).

Модель характеризуется двумя существенными особенностями:

• Пространственная структура, состоящая из иерархии мембран (не пересекающихся) с ассоциированными с ними объектами. Мембрана без каких-либо других мембран внутри называется элементарной.
• Общие правила, описывающие эволюцию структуры: эндоцитоз (перемещение элементарной мембраны внутрь соседней мембраны) и экзоцитоз (перемещение элементарной мембраны за пределы мембраны, где она расположена). Более конкретные правила задаются пиноцитозом (поглощением нулевых внешних мембран) и фагоцитозом (поглощением только одной внешней элементарной мембраны).

Вычисления выполняются следующим образом: начиная с исходной структуры, система развивается, применяя правила недетерминированным и максимально параллельным образом. Правило применимо, когда все задействованные объекты и мембраны, находящиеся в его левой части, доступны. Максимально параллельный способ использования правил означает, что на каждом шаге применяется максимальный мультинабор правил, а именно такой мультинабор правил, к которому нельзя добавить никаких дополнительных правил. Конфигурация остановки достигается, когда ни одно правило не применимо. Результат представлен количеством объектов, связанных с указанной мембраной.

Подвижные мембраны представляют собой формализм, который описывает движение мембран внутри пространственной структуры путем применения правил из заданного набора правил. $R$. Мобильность обеспечивается за счет потребления и перезаписи объектов. В вычислительном отношении работа выполняется с использованием мембранных конфигураций. Набор ${\mathcal {M}}$ конфигураций мембран (ранжированных по $M,N,\dots$) os определяется с помощью свободного моноида $V^{*}$ (ранжируется по $u,v,\dots$), порожденный конечным алфавитом $V$ (ранжируется по $a,b,\dots$):

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

Если $M$ и $N$ представляют собой две мембранные конфигурации, $M$ сводится к $N$ (обозначается $M\rightarrow N$) если существует правило в наборе правил $R$ применимо к конфигурации $M$ так что новая конфигурация $N$ получается. При применении правил $R$, также используются следующие правила вывода:

$\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'}{\displaystyle M\|N\ \rightarrow \ M'\|N'}}$;

$\qquad {\it {(Mem)}}\ {\frac {\displaystyle M\ \rightarrow \ M'}{\displaystyle [\;M\;]_{u}\rightarrow [\;M'\;]_{u}}};\qquad \qquad {\it {(Struc)}}\ {\frac {\displaystyle M\equiv _{mem}M'\quad M'\rightarrow N'\quad \ N'\equiv _{mem}N}{\displaystyle M\rightarrow N}}$

При описании расчета системы мобильных мембран исходная конфигурация $M_{0}$ и набор правил $R$ даны. Правила, используемые в этой статье, описывают ${\it {object~evolution}}$ (перезапись объекта), ${\it {endocytosis}}$ движение (перемещение элементарной мембраны внутрь соседней мембраны), ${\it {exocytosis}}$ движение (перемещение элементарной мембраны за пределы мембраны, где она расположена), ${\it {pinocytosis}}$ (поглощая ноль внешних мембран) и ${\it {phagocytosis}}$ (захватывающий только одну внешнюю элементарную мембрану).

Вычислительная способность мобильных мембран

Особенностью мобильных мембран является то, что эта новая модель, основанная на правилах, подходит для доказательства результатов вычислимости в терминах машин Тьюринга, а не путем сведения к лямбда-исчислению, как в случае исчислений процессов с подвижностью. В этом разделе определены четыре класса мембран, основанные на биологических фактах, и показано, что их вычислительная мощность зависит от исходной конфигурации и набора используемых правил.

Простые мобильные мембраны

Системы простых мобильных мембран (СМ) определяются на множестве конфигураций ${\mathcal {M}}$и развиваются, используя правила эндоцитоза и экзоцитоза , а именно перемещение мембраны внутрь соседней мембраны или за пределы мембраны, где она расположена, соответственно. Эволюция от одной конфигурации к другой осуществляется с использованием правил из набора правил. $R$ определяется следующим образом:

$[[a\;\|\;M]_{m}\;\|\;N]_{k}\rightarrow [[v\;\|\;M]_{m}\;\|\;N]_{k}$, для $k,m\in {\mathcal {N}}$, $a\in V$, $v\in V^{*}$; (локальная эволюция объекта)

$[a\;\|\;M]_{m}\rightarrow [v\;\|\;M]_{m}$, для $m\in {\mathcal {N}}$, $a\in V$, $v\in V^{*}$; (глобальная эволюция объектов)

$[a\;\|\;M_{1}]_{h}\;\|\;[M]_{m}\rightarrow [[b\;\|\;M_{1}]_{h}\;\|\;M]_{m}$, для $h,m\in {\mathcal {N}}$, $a,b\in V$; (эндоцитоз)

$[[a\;\|\;M_{1}]_{h}\;\|\;M]_{m}\rightarrow [b\;\|\;M_{1}]_{h}\;\|\;[M]_{m}$, для $h,m\in {\mathcal {N}}$, $a,b\in V$; (экзоцитоз)

где $M_{1}$ является мультимножеством, и $M$, $N$ представляют собой произвольные конфигурации мембран.

Полноту по Тьюрингу можно получить, используя девять мембран вместе с операциями эндоцитоза и экзоцитоза [21] . В [17] доказано, что четырёх мобильных мембран достаточно, чтобы получить мощность машины Тьюринга, а в [4] количество мембран уменьшено до трёх.

$SM(levol,endo,exo)$ обозначает семейство всех множеств, порождаемых внутри данной мембраны простыми подвижными мембранами с использованием правил локальной эволюции ( $levol$), правила эндоцитоза и экзоцитоза. Всякий раз, когда правит глобальная эволюция ( $gevol$) используются параметр $levol$ заменяется на $gevol$. Если тип правил не используется, то его название в списке опускается. Количество мембран не увеличивается в ходе вычислений, но может уменьшаться при отправке мембран из системы. В этом случае $SM_{n}(gevol,endo,exo)$ обозначает семейство наборов векторов натуральных чисел, вычисляемых с использованием не более $n$ мембран. $RE$ обозначал семейство вычислимых по Тьюрингу множеств векторов, порожденных произвольными грамматиками.

доказано В [17] , что $SM_{4}(gevol,endo,exo)=RE$. Направление исследований, начатое в области мембранных вычислений, направлено на поиск мембранных систем с минимальным набором ингредиентов, которые были бы достаточно мощными, чтобы достичь полной мощности машин Тьюринга. Таким образом, предыдущие результаты, представленные в [17], улучшаются за счет уменьшения количества мембран до трех. Более того, это достигается за счет использования правил локальной эволюции вместо правил глобальной эволюции.

Теорема. $SM_{3}(levol,endo,exo)=RE$.

Доказательство этого результата использует технику, аналогичную использованной в [4] .

Улучшенные мобильные мембраны

Системы усиленных мобильных мембран представляют собой вариант простых мембранных систем, предложенных в [1] для описывающие некоторые биологические механизмы иммунной системы. Операции, управляющие мобильностью систем улучшенной мобильной связи. мембраны - это эндоцитоз (эндо), экзоцитоз (экзо), принудительный эндоцитоз (фендо), принудительный экзоцитоз (фексо). Эволюция от настройка на другой производится с использованием правил из набора правил $R$ определяется следующим образом:

$[u\;\|\;v\;\|\;M]_{h}\;\|\;[v'\;\|\;N]_{m}\!\rightarrow \![w'\;\|\;[w]_{h}]_{m}$ для $h,m\!\in \!{\mathcal {N}};u\!\in \!V^{+},v,v',w,w'\!\in \!V^{*}$; (эндоцитоз)

$[v'\;\|\;N\;\|\;[u\;\|\;v\;\|\;M]_{h}]_{m}\!\rightarrow \![w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}$, для $h,m\!\in \!\!{\mathcal {N}};u\in V^{+},v,v',w,w'\in V^{*}$; (экзоцитоз)

$[v\;\|\;M]_{h}\;\|\;[u\;\|\;v'\;\|\;N]_{m}\!\!\rightarrow \!\![[w\;\|\;M]_{h}\;\|\;w'\;\|\;N]_{m}$ для $h,m\!\!\in \!\!{\mathcal {N}}$, $u\!\in \!V^{+},v,v'\!,w,w'\!\in \!V^{*}$; (усиленный эндоцитоз)

$[u\;\|\;v'\;\|\;[v\;\|\;M]_{h}\;\|\;N]_{m}\!\!\rightarrow \!\![w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}$ для $h,m\!\in \!{\mathcal {N}},u\in V^{+},v,v',w,w'\in V^{*}$; (усиленный экзоцитоз)

\noindent где $M$ является мультимножеством и $N$ представляет собой произвольную конфигурацию мембраны.

Вычислительная мощность систем усиленных мобильных мембран с использованием этих четырех операций изучалась в работе [20] , где доказано, что двенадцать мембран могут обеспечить вычислительную универсальность, а в [4] результат улучшается за счет сокращения числа мембран до девяти. . Стоит отметить, что в отличие от предыдущих результатов, ни в одном из результатов (и их доказательствах) не используется переписывание объекта с помощью контекстно-свободных правил.

Взаимодействие между этими четырьмя операциями довольно мощное, а вычислительная мощность машины Тьюринга достигается с помощью двенадцати мембран без использования контекстно-свободной эволюции объектов [20] .

Семейство всех наборов, генерируемых внутри данной мембраны улучшенными мобильными мембранами степени не более $n$ использование правил $\alpha \subseteq \{exo,endo,fendo,fexo\}$, обозначается $EM_{n}(\alpha )$.

Теорема. $EM_{3}(endo,exo)=EM_{3}(fendo,fexo)$.

Теорема. $EM_{12}(endo,exo,fendo,fexo)=RE$.

При доказательстве результата предыдущей теоремы авторы не использовали оптимальную конструкцию мембранной системы. Далее доказывается, что по тем же правилам ( эндо , экзо , фендо , фексо ) можно построить мембранную систему, используя всего девять мембран вместо двенадцати мембран. Оптимальна ли это конструкция, остается открытым вопрос.

Теорема. $EM_{9}(endo,exo,fendo,fexo)=RE$.

Доказательство аналогично представленному в [4] .

Взаимные мобильные мембраны

Следуя подходу, представленному в [3] , определяются «системы взаимных подвижных мембран», представляющие собой вариант систем простых мобильных мембран, в которых эндоцитоз и экзоцитоз работают всякий раз, когда вовлеченные мембраны «договариваются» о движении; это соглашение описывается с использованием двойных объектов $a$ и ${\overline {a}}$ в вовлеченных мембранах. Операциями, регулирующими подвижность систем взаимных мобильных мембран, являются взаимный эндоцитоз (взаимный эндо) и взаимный экзоцитоз (взаимный экзо). Эволюция от одной конфигурации к другой осуществляется с использованием правил из набора правил. $R$ определяется следующим образом:

$[u\;\|\;v\;\|\;M]_{h}\;\|\;[{\overline {u}}\;\|\;v'\;\|\;N]_{m}\rightarrow [\;[w\;\|\;M]_{h}\;\|\;w'\;\|\;N]_{m}$ для $h,m\in {\mathcal {N}},u,{\overline {u}}\in V^{+},v,v',w,w'\!\!\in V^{*}$; (взаимный эндоцитоз)

$[{\overline {u}}\;\|\;v'\;\|\;N\;\|\;[u\;\|\;v\;\|\;M]_{h}]_{m}\rightarrow [w\;\|\;M]_{h}\;\|\;[w'\;\|\;N]_{m}$ для $h,m\in {\mathcal {N}},u,{\overline {u}}\in V^{+},v,v',w,w'\!\!\in V^{*}$; (взаимный экзоцитоз)

где $M$ является мультимножеством и $N$ представляет собой произвольную конфигурацию мембраны.

Достаточно рассмотреть биологически обусловленные операции взаимного эндоцитоза и взаимного экзоцитоза и трех мембран, чтобы получить полную вычислительную мощность машины Тьюринга [6] . Три также представляют собой минимальное количество мембран, чтобы правильно обсудить движение, обеспечиваемое эндоцитозом и экзоцитозом: работа с конфигурациями, соответствующими системе двух мембран, движущихся внутри кожной мембраны.

Семейство всех наборов, порождаемых внутри данной мембраны взаимными подвижными мембранами степени $n$ использование правил взаимного эндоцитоза ( mendo ) и правил взаимного экзоцитоза ( mexo ) обозначается $MM_{n}(mendo,mexo)$. Таким образом, результат можно сформулировать следующим образом.

Теорема. $MM_{3}(mendo,mexo)=RE$.

В системах простых мобильных мембран с правилами локальной эволюции и правилами подвижности известно, что системы третьей степени имеют ту же мощность, что и машина Тьюринга, а в системах с улучшенными подвижными мембранами, использующими только правила подвижности, степень систем, имеющих ту же мощность, что и машина Тьюринга, машина Тьюринга увеличивается до девяти. В каждом правиле подвижности из систем простых и расширенных подвижных мембран в левой части правил в доказательствах фигурирует только один объект. Путем использования мультимножеств вместо объектов и синхронизации по объектам и кообъектам доказано, что достаточно рассматривать только системы трех взаимно подвижных мембран вместе с операциями взаимного эндоцитоза и взаимного экзоцитоза, чтобы получить полную вычислительную мощность тьюринговского алгоритма. машина.

Доказательство проводится аналогично доказательству вычислительной универсальности систем расширенной мобильной связи. мембраны [20] .

Взаимные мембраны с объектами на поверхности

Мембранные системы [24] и бранное исчисление [10] исходят из одних и тех же наблюдений; однако они созданы с разными целями: мембранные системы формально исследуют вычислительную природу и мощность различных свойств мембран, в то время как исчисление бран способно дать точное и интуитивное представление биологической реальности. В [12] инициаторы этих двух формализмов описывают цели, которые они имели в виду: «Хотя мембранные вычисления представляют собой ветвь естественных вычислений, которая пытается абстрагировать вычислительные модели, в смысле Тьюринга, от структуры и функционирования клетки, используя, в частности, автоматы, язык и инструменты теории сложности, бранные исчисления уделяют больше внимания точности биологической реальности, имеют в качестве основной цели системную биологию и особенно используют структуру алгебры процессов».

В [2] определены системы взаимных мембран с объектами на поверхности, следуя идее добавления объектов на мембрану и используя биологически вдохновленные правила пино/экзо/фаго, взятые из [12,14,18,19] . Объекты и сообъекты используются в правилах фаго и экзо, чтобы проиллюстрировать тот факт, что обе вовлеченные мембраны согласны в движении. Эволюция от одной конфигурации к другой осуществляется с использованием правил из набора правил. $R$ определяется следующим образом:

$[M]_{v\;\|\;a\;\|\;u}\rightarrow [[~]_{u\;\|\;x}\;\|\;M]_{v\;\|\;y}$, для $a\in V,u,v,x,y\in V^{*},ux,vy\in V^{+}$ (пино)

$[[M]_{a\;\|\;u}\;\|\;N]_{{\overline {a}}\;\|\;v}\rightarrow M\;\|\;[N]_{u\;\|\;v\;\|\;x}$, для $,{\overline {a}}\in V,u,v,x\in V^{*},uvx\in V^{+}$ (экзо)

$[M_{1}]_{a\;\|\;u}\;\|\;[N]_{{\overline {a}}\;\|\;b\;\|\;v}\rightarrow [[[M_{1}]_{u\;\|\;x}]_{b}\;\|\;N]_{v\;\|\;y}$, для $a,{\overline {a}},b\!\in \!V,u,v,x,y\in V^{*},ux,vy\in V^{+}$ (пещера)

\noindent где $M_{1}$ является мультимножеством и $M$, $N$ представляют собой произвольные конфигурации мембран.

Исследована вычислительная мощность систем взаимных мембран с объектами на поверхности, управляемых парами правил: пино/экзо или фаго/экзо, доказывая, что они универсальны даже при использовании небольшого количества мембран. Эти случаи уже были исследованы в [19] ; однако лучшие результаты даются за счет увеличения количества мембран. Краткое изложение результатов (существующих и новых) представлено следующим образом:

Сводка результатов

---

Операции	$\qquad$Количество мембран	$\qquad$Масса	$\qquad$РЭ	$\qquad$Где
Сосна, экзо	8	4,3	Да	Теорема 6.1 [19]
Сосна, экзо	3	5,4	Да	Здесь
Пещера, экзо	9	5,2	Да	Теорема 6.2 [19]
Пещера, экзо	9	4,3	Да	Теорема 6.2 [19]
Пещера, экзо	4	6,3	Да	Здесь

В результате расчета рассматривается вектор множественности мультимножества из всех мембран. Таким образом, результат остановки вычислений состоит из всех векторов, описывающих множество объектов со всех мембран; непрерывные вычисления не дают результатов. Количество объектов в правой части правила называется его весом . Семейство всех множеств, порожденных системами взаимных мембран с объектами на поверхности, используемыми в любой момент во время остановки вычислений. максимум $n$ мембраны, и любое из правил $r_{1},r_{2}\in \{pino,exo,phago\}$ веса максимум $r,s$ соответственно, обозначается $MMOS_{n}(r_{1}(r),r_{2}(s)$). Когда один из параметров не ограничен, он заменяется на $*$.

доказано В [19] , что системы из восьми мембран с объектами на поверхности и с использованием пино- и экзоопераций веса четыре и три универсальны. Количество мембран может быть уменьшено с восьми до трех. Однако для этого вес операций пино и экзо увеличивается на единицу, а именно с четырех и трех до пяти и четырех. Это означает, что для того, чтобы с помощью пино- и экзоопераций построить универсальную систему мобильных мембран с объектами на поверхности, нужно решить, хочет ли он минимизировать количество мембран или веса операций.

Теорема. $MMOS_{m}(pino(r),exo(s))=RE$, для всех $m\geq 3,r\geq 5,s\geq 4$.

доказано, В [19] что системы из девяти мембран с объектами на поверхности и с использованием фаго- и экзоопераций веса четыре и три (или пять и два) являются универсальными. Число мембран можно уменьшить с девяти до четырех, но для этого вес фаго- и экзоопераций увеличивают с четырех и трех (или пяти и двух) до шести и трех. При построении полной по Тьюрингу системы мобильных мембран с объектами на поверхности с помощью фаго- и экзоопераций возникает та же проблема, что и при использовании пино- и экзоопераций: выбрать либо минимизацию числа мембран, либо веса операций.

Теорема. $MMOS_{m}(phago(r),exo(s))=RE$, для всех $m\geq 4,r\geq 6,s\geq 3$.

Выразительная сила мобильных мембран

Далее будет показано, что мобильные мембраны обладают, по крайней мере, такой же выразительной силой, как мобильные эмбиенты и бранные камни, за счет кодирования мобильных эмбиентов и бранных камней в определенных системах мобильных мембран.

Встраивание мобильных окружений в мобильные мембраны

Подвижные мембраны и мобильные среды [11] имеют схожее строение и общие концепции. Оба имеют иерархическую структуру, представляющую местоположения, предназначены для описания мобильности и используются при описании различных биологических явлений [10,15] . Мобильные окружения подходят для представления движения окружений через окружения и общения, которое происходит внутри границ окружений. Мембранные системы подходят для представления эволюции объектов и движения объектов и мембран через мембраны. Приведено сравнение этих новых моделей ( мобильных сред и мобильных мембран) и кодирование сред в мембраны. По существу это вложение представлено в [5] .

Безопасные эмбиенты представляют собой вариант мобильного эмбиента , в котором любое перемещение эмбиента происходит только при согласии обоих участников. Мобильность обеспечивается потреблением определенных пар возможностей. Безопасные окружения отличаются от мобильных окружений добавлением совместных действий: если в мобильных окружениях движение инициируется только движущимся окружением и целевое окружение не имеет над ним контроля, в безопасных окружениях оба участника должны договориться, используя сопоставление между действие и сотрудничество. Краткое описание чистой безопасной окружающей среды (SA) приведено ниже; дополнительную информацию можно найти в [22,23] . Учитывая бесконечный набор имен ${\mathcal {N}}$ (ранжируется по $m,n,\dots$), набор ${\mathcal {A}}$ SA-процессов (обозначаемых $A,A',B,B',\dots$) вместе со своими возможностями (обозначаемыми $C,C',\dots$) определяются следующим образом:

$\qquad C::=in\ n\;\mid \;{\overline {in}}\ n\;\mid \;out\ n\;\mid \;{\overline {out}}\ n\;\mid \;open\ n\;\mid \;{\overline {open}}\ n$

$\qquad A::=0\quad \mid \quad A\;\mid \;B\quad \mid \quad C.A\quad \mid \quad n[\;A\;]$

Процесс $0$ это неактивный мобильный окружение. Движение $C.\,A$ обеспечивается возможностью $C$с последующим выполнением $A$. Эмбиент $n[\;A\;]$ представляет собой ограниченное место, помеченное $n$ в котором SA-процесс $A$ выполняется. $A\,\mid \,B$ это параллельная композиция мобильных эмбиентов $A$ и $B$. $(\nu n)A$ создает новое уникальное имя $n$ в рамках $A$. Структурное соответствие $\equiv _{amb}$ над окружениями – это наименьшее соответствие такое, что $({\mathcal {A}},\mid ,0)$ является коммутативным моноидом.

Операционная семантика чистого безопасного исчисления окружающей среды определяется в терминах редукционного отношения $\Rightarrow _{amb}$ по следующим аксиомам и правилам.

Аксиомы:

$(In)\quad n[\;in\ m.A\mid A'\;]\mid m[\;{\overline {in}}\ m.B\mid B'\;]\Rightarrow _{amb}m[\;n[\;A\mid A'\;]\mid B\mid B'\;]$;

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

$(Open)\quad open\ n.A\;\mid \;n[\;{\overline {open}}\ n.B\mid B'\;]\Rightarrow _{amb}A\;\mid \;B\;\mid \;B'$.

Правила:

$(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\Rightarrow _{amb}A'\quad \displaystyle B\Rightarrow _{amb}B'}{\displaystyle A\;\mid \;B\Rightarrow _{amb}A'\;\mid \;B'}}$;

$(Amb)\quad {\frac {\displaystyle A\Rightarrow _{amb}A'}{\displaystyle n[\;A\;]\Rightarrow _{amb}n[\;A'\;]}};\qquad \qquad \qquad \qquad (Struc)\quad {\frac {\displaystyle A\equiv A',\ A'\Rightarrow _{amb}B',\ B'\equiv B}{\displaystyle A\Rightarrow _{amb}B}}$.

$\Rightarrow _{amb}^{*}$ обозначает рефлексивное и транзитивное замыкание бинарного отношения $\Rightarrow _{amb}$.

Перевод из набора ${\mathcal {A}}$ безопасной среды на съемочной площадке ${\mathcal {M}}$ мембранных конфигураций формально задается следующим образом:

Определение. Перевод ${\mathcal {T}}:{\mathcal {A}}\rightarrow {\mathcal {M}}$ дается ${\mathcal {T}}(A)=dlock~{\mathcal {T}}_{1}(A)$, где ${\mathcal {T}}_{1}:{\mathcal {A}}\rightarrow {\mathcal {M}}$ является

$\qquad {\mathcal {T}}_{1}(A)=$${\begin{cases}cap~n\;\|\;[~]_{cap~n}&{\mbox{if }}A=cap~n\\cap~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{cases}}$

Объект $dlock$ размещается рядом с мембранной структурой, чтобы предотвратить потребление объектов возможностей в мембранной системе, которые соответствует мобильному окружению, которое не может развиваться дальше.

Предложение. Структурно конгруэнтная среда преобразуется в структурно конгруэнтные мембранные системы; более того, структурно конгруэнтные транслируемые мембранные системы соответствуют структурно конгруэнтным средам: $\qquad \qquad A\equiv _{amb}B$ если только ${\mathcal {T}}(A)\equiv _{mem}{\mathcal {T}}(B)$.

Рассматривая две мембранные системы $M$ и $N$ только с одним объектом $dlock$, $M\Rightarrow _{mem}N$ если существует последовательность правил $r_{1},\ldots ,r_{i}$, из конкретного набора правил, используемых в [7] , что применение правил из этого набора к мембранной конфигурации $M$ получается конфигурация мембраны $N$.

Предложение. Если $A$ и $B$ это два окружения и $M$ представляет собой мембранную систему, такую ​​что $A\Rightarrow _{amb}B$ и $M={\mathcal {T}}(A)$, то существует набор правил, применимых к $M$ такой, что $M\Rightarrow _{mem}N$, и $N={\mathcal {T}}(B)$.

Предложение. Позволять $M$ и $N$ быть двумя мембранными системами только с одним $dlock$ объект и окружающая среда $A$ такой, что $M={\mathcal {T}}(A)$. Если существует свод правил, применимых к $M$ такой, что $M\Rightarrow _{mem}N$, то существует окружающая среда $B$ с $A\Rightarrow _{amb}^{*}B$ и $N={\mathcal {T}}(B)$. Количество пар незвездных объектов, потребляемых в мембранных системах, равно количеству пар способностей, потребляемых в амбиентах.

Теорема. (оперативная переписка)

• Если $A\Rightarrow _{amb}B$, затем ${\mathcal {T}}(A)\Rightarrow _{mem}{\mathcal {T}}(B)$.
• Если ${\mathcal {T}}(A)\Rightarrow _{mem}M$, тогда существует $B$ такой, что $A\Rightarrow _{amb}B$ и $M={\mathcal {T}}(B)$.

Встраивание бранового исчисления в мобильные мембраны

Рассмотрен фрагмент бранного исчисления, названный ПЭП, и взаимные подвижные мембраны с объектами на поверхности как вариант систем с подвижными мембранами. Подвижные мембраны с объектами на поверхности вдохновлены моделью мембранной системы, представленной в [12], в которой объекты прикреплены к мембранам. Моделирование PEP-фрагмента исчисления бран с использованием взаимного представлены мембраны с объектами на поверхности. Этот подход связан с некоторыми другими работами, пытающимися показать связь между мембранными системами и исчислением бран [8,9,14,18,19] .

Как сказано в [24] , «на первый взгляд роль объектов, помещенных на мембраны, в мембранных и бранных системах различна: в мембранных компьютингах основное внимание уделяется эволюции самих объектов, тогда как в бранных исчислениях — объектов (« белки») главным образом контролируют эволюцию мембран». Определив кодировку PEP-фрагмента исчисления бран во взаимных мембранах с объектами на поверхности, показано, что разница между двумя моделями несущественна. Другое различие в семантике двух формализмов выражено в [8] : «в то время как исчисления на бранах обычно оснащены чередующейся последовательной семантикой (каждый вычислительный шаг состоит из выполнения одной инструкции), обычная семантика в мембранных вычислениях такова: на основе максимального параллелизма (вычислительный шаг состоит из максимального набора независимых взаимодействий)».

Брановое исчисление [10] изучает мембраны, представляющие собой места активности; таким образом, вычисление происходит на поверхности мембраны. Действия двух основных бранных камней: пино, экзо, фаго (PEP) и mate, drop, Bud (MBD) напрямую зависят от биологических процессов, таких как эндоцитоз, экзоцитоз и митоз. Последние операции можно смоделировать с использованием первой [10] .

Пино/экзо/фаговое исчисление – его синтаксис

---

Системы	$P,Q$	$::\,=$	$P\circ Q\;\mid \;\sigma (~)\;\mid \;\sigma (P)$	гнезда из перепонок
Браны	$\sigma ,\tau$	$::\,=$	$O\;\mid \;\sigma \mid \tau \;\mid \;a.\sigma$	комбинации действий
Действия	$a,b$	$::\,=$	$n^{\searrow }\;\mid \;{\overline {n}}^{\searrow }(\sigma )\;\mid \;n^{\nwarrow }\;\mid \;{\overline {n}}^{\nwarrow }\;\mid \;pino(\sigma )$	фаго $\searrow$, экзо $\nwarrow$

Мембраны состоят из участков, где участок $s$ можно составить из других патчей $s=s_{1}\;\mid \;s_{2}$. Элементарный патч $s$ состоит из действия $a$ за которым, после его использования, следует еще один патч $s_{1}s=a.s_{1}$. Действия часто происходят в комплементарных парах, которые вызывают взаимодействие между мембранами. Имена $n$ используются для объединения действий и совместных действий. Карделли мотивирует, что оператор репликации используется для моделирования понятия «множества» компонентов одного и того же вида, что на самом деле является стандартной ситуацией в биологии [10] . Оператор репликатора не используется, поскольку мембранную систему невозможно определить, не зная точно исходной структуры мембраны. ${\mathcal {P}}$ обозначает набор систем бран, определенных выше. Можно сделать некоторые сокращения: $a.0$ как $a$, $0(P)$ как $(P)$, и $0(~)$ как $(~)$.

Отношение структурной конгруэнтности — это способ перестройки системы, при котором взаимодействующие части объединяются, как показано на рисунке. в следующем:

Пино/экзо/фаговый исчисление – структурное соответствие

---

$P\circ Q\equiv _{b}Q\circ P$	$\qquad \qquad$	$\sigma \;\mid \;\tau \equiv _{b}\tau \;\mid \;\sigma$
$P\circ (Q\circ R)\equiv _{b}(P\circ Q)\circ R$	$\qquad \qquad$	$\sigma \;\mid \;(\tau \;\mid \;\rho )\equiv _{b}(\sigma \;\mid \;\tau )\;\mid \;\rho$
$\qquad$	$\qquad \qquad$	$\sigma \;\mid \;0\equiv _{b}\sigma$
$\qquad$	$\qquad \qquad$	$\qquad$
$P\equiv _{b}Q{\mbox{implies }}P\circ R\equiv _{b}Q\circ R$	$\qquad \qquad$	$\sigma \equiv _{b}\tau {\mbox{implies }}\sigma \;\mid \;\rho \equiv _{b}\tau \;\mid \;\rho$
$P\equiv _{b}Q{\mbox{and }}\sigma \equiv _{b}\tau {\mbox{implies }}\sigma (P)\equiv _{b}\tau (Q)$	$\qquad \qquad$	$\sigma \equiv _{b}\tau {\mbox{implies }}a.\sigma \equiv _{b}a.\tau$

Ниже представлены правила редукции исчисления:

Исчисление Pine/Exo/Phago — правила редукции

---

$pino(\rho ).\sigma \mid \sigma _{0}(P)\rightarrow _{b}\sigma \mid \sigma _{0}(\rho (~)\circ P)$	$\qquad \qquad$	(Пино)
${\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)$	$\qquad \qquad$	(Экзо)
$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)$	$\qquad \qquad$	(Фаго)
$P\rightarrow _{b}Q{\mbox{implies }}P\circ R\rightarrow _{b}Q\circ R$	$\qquad \qquad$	(о)
$P\rightarrow _{b}Q{\mbox{implies }}\sigma (P)\rightarrow _{b}\sigma (Q)$	$\qquad \qquad$	(Брана)
$P\equiv _{b}P'{\mbox{and }}P'\rightarrow _{b}Q'{\mbox{and }}Q'\equiv _{b}Q{\mbox{implies }}P\rightarrow _{b}Q$	$\qquad \qquad$	(Структура)

Действие $pino(\rho )$ создает пустой пузырь внутри мембраны, где $pino$ действие проживает; представьте, что исходная мембрана прогибается внутрь и отщипывается. Патч $\sigma$ на пустом пузыре является параметром $pino$. Экзо-экшн $n^{\nwarrow }$, который сопровождается дополнительным совместным действием ${\overline {n}}^{\nwarrow }$, моделирует слияние двух вложенных друг в друга мембран, которое начинается с соприкосновения мембран в определенной точке. В процессе (который является плавным, непрерывным процессом) подсистема $P$ выбрасывается наружу, и все остаточные участки двух мембран сближаются. Действие фаго $n^{\searrow }$, который также сопровождается дополнительным совместным действием ${\overline {n}}^{\searrow }(\rho )$, моделирует мембрану (та, у которой $Q$) «съедает» другую мембрану (ту, у которой $P$). Опять же, этот процесс должен быть плавным и непрерывным, поэтому он биологически реализуемый. Оно протекает по $Q$ мембрана, охватывающая $P$ мембрану и присоединяется к себе с другой стороны. Таким образом, вокруг съеденной мембраны создается дополнительный слой мембраны: участок на этой мембране задается параметром $\rho$ кофагодействия (аналогично параметру пинодействия).

Перевод из набора ${\mathcal {P}}$ бранных процессов к множеству ${\mathcal {M}}$ мембранных конфигураций формально задается следующим образом:

Определение Перевод ${\mathcal {T}}:{\mathcal {P}}\rightarrow {\mathcal {M}}$ дается

${\mathcal {T}}(P)=$ ${\begin{cases}\;[~]_{{\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{cases}}$

где ${\mathcal {S}}:{\mathcal {P}}\rightarrow V^{*}$ определяется как:

${\mathcal {S}}(\sigma )=$ ${\begin{cases}\sigma &{\mbox{if }}\sigma =n^{\searrow }or\sigma =n^{\nwarrow }or\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{cases}}$

Правила систем взаимных мембран с объектами на поверхности (MMOS) представлены ниже.

Пино/Экзо/Фаго Правила MMOS

---

Пино	$\qquad \qquad$	$[M]_{S(pino(\rho ).\sigma \mid \sigma _{0})}\rightarrow [[~]_{S(\rho )}\;\|\;M]_{S(\sigma \mid \sigma _{0})}$
Экзо	$\qquad \qquad$	$[[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})}$
Пещера	$\qquad \qquad$	$[M_{1}]_{S(n^{\searrow }.\sigma \mid \sigma _{0})}\;\|\;[N]_{S({\overline {n}}^{\searrow }(\rho ).\tau \mid \tau _{0})}\rightarrow [[[M_{1}]_{S(\sigma \mid \sigma _{0})}]_{S(\rho )}\;\|\;N]_{S(\tau \mid \tau _{0})}$

где $M_{1}$ является мультимножеством и $M$, $N$ представляют собой произвольные конфигурации мембран.

Следующий результат утверждает, что две структурно эквивалентные системы ПЭП транслируются в системы взаимных мембран с структурно эквивалентными объектами на поверхности.

Предложение. Если $P$ представляет собой систему PEP и $M={\mathcal {T}}(P)$ представляет собой систему взаимных мембран с объектами на поверхности, то существует $N$ такой, что $M\equiv _{m}N$ и $N={\mathcal {T}}(Q)$, в любое время $P\equiv _{b}Q$.

Предложение. Если $P$ представляет собой систему PEP и $M={\mathcal {T}}(P)$ представляет собой систему взаимных мембран с объектами на поверхности, то существует $Q$ такой, что $N={\mathcal {T}}(Q)$ в любое время $M\equiv _{m}N$.

Замечание. В последнем предложении возможно, что $P\not \equiv _{b}Q$. Предполагать $P=n^{\searrow }.n^{\nwarrow }(~)$. Путем перевода получается, что $M={\mathcal {T}}=[~]_{n^{\searrow }\;\|\;n^{\nwarrow }}\equiv _{m}[~]_{n^{\nwarrow }\;\|\;n^{\searrow }}=N$. Возможно иметь $Q=n^{\nwarrow }.n^{\searrow }(~)$ или $Q=n^{\nwarrow }\mid n^{\searrow }(~)$ такой, что $N={\mathcal {T}}(Q)$, но $P\not \equiv _{b}Q$.

Предложение. Если $P$ представляет собой систему PEP и $M={\mathcal {T}}(P)$ представляет собой систему взаимных мембран с объектами на поверхности, то существует $N$ такой, что $M\rightarrow N$ и $N={\mathcal {T}}(Q)$, в любое время $P\rightarrow _{b}Q$.

Предложение. Если $P$ представляет собой систему PEP и $M={\mathcal {T}}(P)$ представляет собой систему взаимных мембран с объектами на поверхности, то существует $Q$ такой, что $N={\mathcal {T}}(Q)$ в любое время $M\rightarrow N$.

Следующее замечание является следствием того, что формализм, использующий семантику перемежения, транслируется в формализм, работающий параллельно.

Замечание. Последнее предложение позволяет $P\not \rightarrow _{b}Q$. Давайте предположим $P={\overline {n}}^{\nwarrow }.{\overline {n}}^{\nwarrow }(n^{\nwarrow }.n^{\searrow }(~))$. Путем перевода получается, что $M=((~)_{n^{\nwarrow }\;\|\;n^{\searrow }})_{{\overline {n}}^{\nwarrow }\;\|\;{\overline {n}}^{\nwarrow }}$, такой, что $M\rightarrow [~]_{n^{\searrow }\;\|\;{\overline {n}}^{\nwarrow }}$. Можно заметить, что существуют $Q=n^{\searrow }.{\overline {n}}^{\nwarrow }(~)$ такой, что $N={\mathcal {T}}(Q)$, но $P\not \rightarrow _{b}Q$.

Эти результаты вместе с их доказательствами представлены в [2] .

Ссылки

1. Б. Аман, Г.Чобану. Описание иммунной системы с использованием улучшенных мобильных мембран. Электр. Заметки в теоретической информатике , том 194(3), 5–18, 2008 г.
2. Б. Аман, Г.Чобану. Мембранные системы с поверхностными объектами. Учеб. Международного семинара по вычислениям с помощью биомолекул (CBM 2008) , 17–29, 2008 г.
3. Б. Аман, Г.Чобану. Конкуренция ресурсов и синхронизация в мембранах. Труды SYNASC08 , Компьютерное общество IEEE, 145–151, 2009.
4. Б. Аман, Г.Чобану. Простые, расширенные и взаимные мобильные мембраны. Труды по вычислительной системной биологии XI', LNBI, том 5750, 26–44, 2009.
5. Б. Аман, Г.Чобану. Перевод мобильной среды в P-системы. Электр. Заметки в теоретической информатике , том 171(2), 11–23, 2007.
6. Б. Аман, Г.Чобану. Полнота по Тьюрингу с использованием трех мобильных мембран. Конспекты лекций по информатике , том 5715, 42–55, 2009 г.
7. Б. Аман, Г. Чобану. О взаимосвязи мембран и окружающей среды. Биосистемы , том 91(3), 515–530, 2008.
8. Н. Буси. О вычислительной мощности бранного исчисления Mate/Bud/Drip: чередование против максимального параллелизма. Конспекты лекций по информатике , том 3850, Springer, 144–158, 2006.
9. Н. Бузи, Р. Горрьери. О вычислительной мощности исчислений Брана. Третий семинар по вычислительным методам в системной биологии , 106–117, 2005 г.
10. Л. Карделли. Бране исчисление. Взаимодействия биологических мембран. Конспекты лекций по биоинформатике , том 3082, 257–278, Springer, 2004.
11. Л. Карделли, А. Гордон. Мобильный окружение. Конспекты лекций по информатике , том 1378, Springer, 140–155, 1998.
12. Л. Карделли, Г.Х. Паун. Результат универсальности для (мем)бранного исчисления, основанного на операциях сопряжения/капления. Стажер. J. Основы компьютерных наук , том 17 (1), 49–68, 2006 г.
13. Л. Карделли, С. Прадалье. Где мембраны встречаются с комплексами. БиоКонкур , 2005.
14. М. Кавальер, С. Седвардс. Мембранные системы с периферическими белками: транспорт и эволюция. Электр. Заметки в теоретической информатике , том 171(2), 37–53, 2007.
15. Г. Чобану, Г. Паун, М. Дж. Перес-Хименес. Применение мембранных вычислений . Спрингер, 2006.
16. Дж. Дассов, Г.Х. Паун. Регулируемое переписывание в теории формального языка . Спрингер-Верлаг, 1990.
17. С. Н. Кришна. Сила мобильности: достаточно четырех мембран. Конспекты лекций по информатике , том 3526, 242–251, Springer, 2005.
18. С. Н. Кришна. Мембранные вычисления с транспортными и встроенными белками. Теоретическая информатика , том 410, 355–375, 2009.
19. С. Н. Кришна. Результаты универсальности для P-систем, основанные на операциях бранного исчисления. Теоретическая информатика , том 371, 83–105, 2007.
20. С.Н. Кришна, Г. Чобану. О вычислительной мощности улучшенных мобильных мембран. Конспекты лекций по информатике , том 5028, 326–335, 2008.
21. С.Н. Кришна, Г.Х. Паун. П-системы с мобильными мембранами. Natural Computing , том 4(3), 255–274, 2005.
22. Ф. Леви, Д. Санджорджи. Управление помехами в окружающей среде. Труды POPL'00 , ACM Press, 352–364, 2000.
23. Ф. Леви, Д. Санджорджи. Мобильная безопасная среда. АСМ ТОПЛАС , том 25, 1-69, 2003.
24. Мистер Пикок. Мембранные вычисления. Введение. Шпрингер-Верланг, Берлин, 2002 г.
25. Гх. Паун. Мембранные вычисления и бранное исчисление (некоторые личные заметки). Электр. Заметки в теоретической информатике , том 171, 3–10, 2007.