We study variants of P systems that are working in the sequential mode. Usually, they are not computationally complete, but there are possible extensions that can increase the computation power. Extensions that implement a notion of zero-checking are often computationally complete. P systems with an ability to create new membranes are a rare exception as they are known to be computationally complete even in the sequential mode without using a dedicated zero-check operation. Using sets instead of multisets was inspired by Reaction systems and we show how to use this relaxation in the context of active membranes. We challenge the original definition of a membrane creation because possible multiplicity of labels of child membranes are in conflict with no multiplicity of objects in Reaction systems. We propose more suitable notions of membrane creation and prove computational completeness by simulating a register machine.
Membrane systems (P systems) [
Standard models of membrane systems have configurations, where any given compartment is represented as a multiset of objects and each computational action is represented by a multiset of simultaneously executed (multiple copies of) individual evolution rules.
Such strong reliance on counting (through multiple copies of objects and rules) may lead to potential problems in two respects. First, one may wonder how realistic is the counting (multiset) mechanism if one needs to represent huge numbers of molecules ⋆ Work supported by the grant VEGA 1/1333/12. and instances of biochemical reactions. Second, a membrane system would normally have an infinite state space, making the application of formal verifiation techniques impratical or indeed impossible (there exists a rich body of results proving Turing completeness of even very simple kinds of membrane systems).
A radical solution to the state space problems can be provided by reaction systems, which, however, model biochemial reactions in living cells using qualitative (based on presence and absence of entities) rather than quantitative rewriting rules.
Set membrane systems [
Alhazov in [
The sequential mode was only mentioned in [
In section 2 we recall some computer science basic notions that we will use through the work. Sequential P systems with active membranes working on sets instead of multisets (Sequential active set P systems) are formally presented in section 3.
In section 4 we show the computational completeness by simulating the register machine. In the last section we propose two modifications of the definition of a membrane creation because in the original definition possible multiplicity of labels of child membranes are in conflict with no multiplicity of objects. First modification is called inject-or-create and has no explicit membrane creation rule. Instead, when sending objects to a child membrane, which does not exist, then a new membrane is created and objects are sent to it. Second modification is called wrap-or-create and has an explicit membrane creation rule. However, applying such rule when a child membrane with the same label exists wraps the existing membrane in the newly created one. 2
Here we recall several notions from the classical theory of formal languages.
An alphabet is a finite nonempty set of symbols. Usually, it is denoted by Σ. A string over an alphabet is a finite sequence of symbols from the alphabet. We denote by Σ∗ the set of all strings over an alphabet Σ. By Σ+ = Σ∗ − {ε} we denote the set of all nonempty strings over Σ. A language over the alphabet Σ is any subset of Σ∗.
The number of occurrences of a given symbol a ∈ Σ in the string w ∈ Σ∗ is denoted by |w|a. ΨΣ (w) = (|w|a1 , |w|a2 , . . . , |w|an ) is called a Parikh vector associated with the string w ∈ Σ∗, where Σ = {a1, a2, . . . , an}. For a language L ⊆ Σ∗, ΨΣ (L) = {ΨΣ (w)|w ∈ L} is the Parikh image of L. If FL is a family of languages, PsFL denotes the family of Parikh images of languages in FL.
A rooted tree is a tree, in which a particular node is distinguished from the others and called the root node. Let T be a rooted tree. We will denote its root node by rT . Let d be a node of T \ {rT }. As T is a tree, there is a unique path from d to rT . The node adjacent to d on that path is also unique and is called a parent node of d and is denoted by parentT (d). We will denote the set of nodes of T by V (T ) and set of its edges by E(T ). Let T1, T2 be rooted trees. A bijection f : V (T1) → V (T2) is an isomorphism iff {(f (u), f (v))|(u, v) ∈ E(T1)} = E(T2) and f (rT1 ) = rT2 . 3
The fundamental ingredient of a P system is the membrane structure (see [
A P system consists of a membrane structure, where each membrane is labeled with a number from 1 to m. Each membrane contains a set of objects. Objects can be transformed into other objects and sent through a membrane according to given rules defined for membrane labels. The rules are known from the beginning for each possible membrane, even for the ones that do not exist yet, or the ones that will never exist.
In this paper we work with sequential P systems with active membranes working on sets (Sequential active set P systems). The rules can modify the membrane structure by dissolving and creating new membranes. That is why we will define the configuration to include the membrane structure as well.
Let Σ be a set of objects. A membrane configuration is a tuple (T, l, c), where: • T is a rooted tree, • l ∈ NV (T ) is a mapping that assigns for each node of T a number (label), where l(rT ) = 1, so the skin membrane is always labeled with 1, • c ∈ (2Σ )V (T ) is a mapping that assigns for each node of T a set of objects from Σ, so it represents the contents of the membrane.
The common representation of a membrane structure in this paper is by a string, where a membrane is denoted by a pair of matching square brackets, e.g. [1[2ab]2ac]1.
A sequential active set P system is a tuple (Σ, C0, R1, R2, . . . , Rm), where: • Σ is a set of objects, • C0 is the initial membrane configuration, • R1, R2, . . . , Rm are finite sets of rewriting rules associated with the labels 1, 2, . . . , m and can be of forms: · u → w, where u ⊆ Σ, |u| ≥ 1, w ⊆ (Σ × {·, ↑, ↓j }) and 1 ≤ j ≤ m, · a dissolving rule u → wδ, where u ⊆ Σ, |u| ≥ 1, w ⊆ (Σ × {·, ↑, ↓j }) and 1 ≤ j ≤ m,
For the first two forms, each rewriting rule may specify for each object on the right side, whether it stays in the current region (we will omit the symbol ·), moves through the membrane to the parent region (↑) or to a specific child region (↓j , where j is a label of a membrane). We denote these transfers with an arrow immediately after the symbol. An example of such rule is the following: ab → ab ↓2 c ↑ cδ.
By applying the rule we mean the removal of objects specified on the left side and the addition of the objects on the right side with respect to set union semantics. Symbol δ ∈/ Σ does not represent an object. It may be present only at the end of the rule, which means that after the application of the rule, the membrane is dissolved and its contents (objects, child membranes) are propagated to the parent membrane.
Active P systems differ from classic (passive) P systems in their ability to create new membranes by rules of the third form. Such rule will create new child membrane with a given label j and a given set of objects v1 as its contents, while the set v2 is the set of products that stays in the current membrane. If the current membrane already contains a child membrane with label j, then such rule is not applicable.
For a sequential active set P system (Σ, C0, R1, R2, . . . , Rm), configuration C = (T, l, c), membrane d ∈ V (T ) the rule r ∈ Rl(d) is applicable iff: • r = u → w and u ⊆ c(d) and for all (a, ↓k) ∈ w there exists d2 ∈ V (T ) such that l(d2) = k ∧ parent(d2) = d, • r = u → wδ and u ⊆ c(d) and for all (a, ↓k) ∈ w there exists d2 ∈ V (T ) such that l(d2) = k ∧ parent(d2) = d and d 6= rT , • r = u → [j v1]j v2 and u ⊆ c(d).
In this paper we assume only sequential systems, so in each step of the computation, there is one rule nondeterministically chosen among all applicable rules in all membranes to be applied.
A computation step of a sequential active P system is a relation ⇒ on the set of membrane configurations such that C1 ⇒ C2 holds iff there is an applicable rule in a membrane in C1, such that applying that rule can result in C2.
The P system can work in generating or in accepting mode. For the generating mode we consider the concatenation of the objects which leave the system, in the order they are sent out of the skin membrane (if several symbols are expelled at the same time, then any ordering of them is considered). In this case we generate a language. The result of a single computation is clearly only one multiset or a string, but for one initial configuration there can be multiple possible computations. It follows from the fact that there can be more than one applicable rule in each configuration and they are chosen nondeterministically.
For the accepting mode the input word is encoded into a membrane structure by a
given encoding and it is accepted if and only if a given accepting configuration can be
reached[
In this section we will show that sequential active set P systems are powerful computing devices as they can simulate the register machine. The section starts with a definition of deterministic register machine with a definition of a configuration. Next is the formulation of the main theorem followed by a proof made by a simulation. At last the efficiency of the simulation is questioned and various improvements are proposed. Definition 1. A n-register machine is a tuple M = (n, P, i, h), where: • n is the number of registers, • P is a set of labeled instructions of the form j : (op(r), k, l), where op(r) is an operation on register r ≤ n, and j, k, l are labels from the set Lab(M ) such that there are no two instructions with the same label j, • i is the initial label, and • h is the final label.
The machine is capable of the following instructions: • (add(r), k, l) : Add one to the contents of register r and proceed to instruction k or to instruction l; in the deterministic variants usually considered in the literature we demand k = l. • (sub(r), k, l) : If register r is not empty, then subtract one from its contents and go to instruction k, otherwise proceed to instruction l. • halt : This instruction stops the machine. This additional instruction can only be assigned to the final label h.
We will denote by (op(r), _, _) any of the operations add and sub operating on the register r having arbitrary following instruction.
A deterministic m-register machine can analyze an input (n1, . . . , nm) ∈ N0m in registers 1 to m, which is recognized if the register machine finally stops by the halt instruction with all its registers being empty (this last requirement is not necessary). If the machine does not halt, the analysis was not successful.
A configuration of a register machine is a tuple (r1, . . . , rm, ip), where ri is the value of the register i and ip (instruction pointer) is the label of current instruction to be executed. 4.2
Theorem 1. Sequential active set P systems are computationally complete. Proof. Computational completeness is proved by a direct simulation of a register machine, which is also computationally complete.
For a register machine with m registers we will construct a sequential active set P system (Σ, C0, R1, . . . Rm+1), where
Σ = {xj , yj for instructions with label j} ∪ {ti for each register i} . Skin membrane will be labeled with m + 1, other labels correspond to registers 1 to m. C0 will be the input word for the register machine encoded into a membrane structure by the following encoding:
For a configuration of register machine (r1, r2, . . . rm, ip) the membrane structure will consist of a skin membrane, which will contain m chains consisting of ri membranes embedded one into another like in a Matryoshka doll with label i. The innermost membranes will contain a single object ti. If ri = 0 then ti is in the skin membrane and there is no membrane with label i. Object representing the label of the current instruction (xip) is in the skin membrane.
We will have following rules in the skin membrane: 1. yj → xj , 2. xj → xj ↓i for instruction j : (op(i), _, _), 3. xj , ti → [1yk, ti]1 for instruction j : (add(i), k, k), 4. xj , ti → l for instruction j : (sub(i), _, l)
For the membrane i: 5. xj → xj ↓i for instruction j : (op(i), _, _), 6. xj , ti → [1yk, ti]1 for instruction j : (add(i), k, k), 7. yj → yj ↑ for instruction j : (op(i), _, _), 8. xj , ti → yk, ti, δ for instruction j : (sub(i), k, l)
Object xj represents the instruction currently executed. It is sent down the chain of membranes by rules 2 and 5. In the innermost membrane the creation of a new membrane (rule 6), or the dissolution (rule 8) is performed. Then the next instruction represented by object yj is sent upwards all the way to the skin membrane by the rule 7. The object ti is always present in the innermost membrane. For a SUB instruction there are two rules in the skin membrane, together they implement the zero-test. The rule 2 is applicable only if the register is nonempty and the rule 4 is applicable only if the register is empty by requiring the presence of ti, meaning that the value of register i is zero. ⊔⊓ Example 1. Assume a register machine with two registers with values r1 = 2, r2 = 0 and the current instruction j : add(1, k, k). The corresponding membrane configuration is [3[1[1t1]1]1xj t2]3. The computation of the P system is deterministic, at each step there is only one applicable rule. Starting with the rule 2 and then the rule 5, xj enters the innermost membrane, where the rule 6 creates new membrane.
The simulation was quite straightforward. We proved that the model is computationally complete. However, the simulation is not very effective. It uses alphabet of size 2 ∗ number of instructions + number of registers, and its number of membranes is linearly dependent on the sum of values of registers. The time needed for executing an instruction on register i is linearly dependent on ri.
In this subsection we address the inefficient usage of membranes in the previous simulation. New, optimized simulation will reduce it to logarithmic dependency.
For a register machine with m registers we will construct a seqeuntial active set P system, where Σ = {0, 1, p, s, t} ∪ {xj , yj , zj for instructions with label j}. Skin membrane will be labeled with m + 1, other labels correspond to registers 1 to m.
Assume configuration of register machine (r1, r2, . . . rm, ip). For each register i, let b1b2 . . . bk be a binary representation of ri. The skin membrane will contain a chain of k membranes embedded one into another like in a Matryoshka doll with label i. The membrane in depth d will contain the object bk−d, which is either 0 or 1. So the highest-order position in the binary number is represented by the innermost membrane and more often changed positions by increments are in membranes closer to the skin membrane. Moreover, the innermost membranes contain a single object t. The skin membrane contains the label of the current instruction xip. Other membranes (not skin and not innermost) contain s. Object p will be in all membranes except the skin membrane and direct children of the skin membrane. It represents the fact that the membrane can be dissolved, while keeping at least one membrane for binary representation of the register value.
The basic idea is to recursively decide the next action based on lowest position. For incrementing number ending with zero, incrementing the lowest position is enough. Similar simple case is when decrementing number ending with one. For incrementing number ending with one, we decrement the lowest position and recursively call increment on the binary number omitting the lowest position. Similarly, for decrementing number ending with zero, we increment the lowest position and recursively call decrement on the binary number omitting the lowest position. There are some special cases, like incrementing 111 to 1000 or decrementing 1000 to 111. In these cases we should change the number of membranes representing positions.
We will have following rules in the skin membrane: 1. yj → xj , 2. xj → xj ↓i for instruction j : op(i, _, _)
For the membrane i and instruction j: 3. yj → yj ↑ (return the next instruction to the skin membrane).
For the membrane i and instruction j : add(i, k, k): 4. xj 1 → xj ↓i 0 (we decremented lower position, so we must increment higher position (011 to 100, now at 1 to 0)), 5. xj 0 → yk ↑ 1 (we incremented a position and can return and proceed to the next instruction), 6. xj 1t → [i1tp]iyk ↑ 0s (incrementing 111 to 1000).
For the membrane i and instruction j : sub(i, k, l): 7. xj 1s → yk ↑ 0s (we found position to decrement, proceed to the next instruction), 8. xj 0 → xj ↓i 1 (1000 is decremented to 0111 and now we encountered a 0), 9. xj 1tp → zktδ (decrementing the number of bits), 10. zj st → yj t (after decremented the number of bits, remove s in the new highestorder position), 11. xj 0t → yl ↑ 0t (trying to decrement a zero) Example 2. Assume a register machine with two registers with values r1 = 3, r2 = 0 and the current instruction j : add(1, k, k). The corresponding membrane configuration is [3[1[11tp]11s]1[20t]2xj ]3. The computation of the P system is deterministic, at each step there is only one applicable rule. Starting with the rule 2, xj will meet the object 1 in the configuration [3[1[11tp]11xj s]1[20t]2]3. The only applicable rule then is 4, resulting in [3[1[11tpxj ]10s]1[20t]2]3. xj now meets objects 1 and t, which means that the only applicable rule is 6, creating a new innermost membrane and resulting in the configuration [3[1[1[11tp]10]10yks]1[20t]2]3. The object yk is by the rule 3 propagated to the skin membrane, where it is prepared for the next instruction by the rule 1.
One instruction of the register machine is performed by number of computational steps which is logarithmic on the value of the register the instruction is operated on. The number of membranes is logarithmic as well. The number of objects is 3 ∗ number of instructions + 5. 4.4
Could the simulation be optimized even more? Encoding the register value to a chain of
membranes is not making full use of membrane structure. There are many options for a
represention of an integer by a tree. For efficient implementation of the increment and
decrement instructions, we need an encoding with a property that a local change in the
value of the encoding of the entire tree corresponds to a local change in the value of the
encodings of its child subtrees. Stein in 1999 [
In this section we will investigate the effect of other semantics of membrane creation. The previous semantics assumed an explicit membrane creation rule. If the current membrane already contains child membrane with the same label as the membrane about to be created, then the rule is not applicable, and the membrane creation is aborted. Similar behavior is in the definition of sending objects to the child membrane. If such membrane does not exist, objects cannot be sent and the rule is not applicable.
These two behaviors are in fact complementary. It seems natural to join these two artificial rule abortions and provide a rule that will always be applicable if the precondition of left side inclusion is fulfilled.
We will first examine the case where we have no explicit membrane creation rule. Any rule which is sending some objects to child membrane labeled j will create child membrane j if it does not exist.
Formally, rules can be of form: • u → w, where u ⊆ Σ, |u| ≥ 1, w ⊆ (Σ × {·, ↑, ↓j }) and 1 ≤ j ≤ m, • a dissolving rule u → wδ, where u ⊆ Σ, |u| ≥ 1, w ⊆ (Σ × {·, ↑, ↓j }) and 1 ≤ j ≤ m.
For a sequential active set P system (Σ, C0, R1, R2, . . . , Rm), configuration C = (T, l, c), membrane d ∈ V (T ) the rule r ∈ Rl(d) is applicable iff: • r = u → w and u ⊆ c(d), • r = u → wδ and u ⊆ c(d) and d 6= rT .
Example 3. Assume the membrane configuration [1[
If we apply the rule a → a ↓3 in the skin membrane, a new membrane labeled 3
is created, because such child membrane does not exist yet. The resulting membrane
configuration is [1[
Theorem 2. Sequential active set P systems with inject-or-create semantics are computationally complete.
Proof. The simulation is essentially the same as in section 4.3. All the rules which are sending objects into a child membrane are already assuming that the child membrane already exists. The only difference is in the rule for membrane creation: xj 1t → [i1tp]iyk ↑ 0s. This rule is applied always in the innermost membrane with no child membranes. Modified simulation will therefore use rule xj 1t → 1 ↓i t ↓i p ↓i yk ↑ 0s, which, when applied, creates a child membrane i, because no such child membrane exists. ⊔⊓
The efficiency of this simulation is essentially the same as in section 4.3, that means logarithmic number of steps for simulating one instruction of the register machine as well as logarithmic number of membranes and the number of objects is 3 ∗ number of instructions + 5. 5.2
In this variant we stay with explicit membrane creation rule, but when the membrane with the same label is already contained in the current membrane, the rule remains applicable and the child membrane will be wrapped by a new membrane with the given contents. For example, applying the rule a → [2b]2c in the membrane 1 of membrane structure [1a[2d]2]1 would result in [1c[2b[2d]2]2]1. Theorem 3. Sequential active set P systems with wrap-or-create semantics are computationally complete.
Proof. Again, we will show how to simulate the register machine. The simulation will be similar to the one defined in subsection 4.2, but with additional control objects similar to the second simulation 4.3.
For a register machine with m registers we will construct a sequential active set P system (Σ, C0, R1, . . . Rm+1), where
Σ = {xj for instructions with label j} ∪ {ti, si for each register i} . Skin membrane will be labeled with m + 1, other labels correspond to registers 1 to m. C0 will be the input word for the register machine encoded into a membrane structure by the following encoding:
For a configuration of register machine (r1, r2, . . . rm, ip) the membrane structure will consist of a skin membrane, which will contain m chains consisting of ri membranes embedded one into another like in a Matryoshka doll with label i. Membranes with a child labeled i will contain a single object si. If the membrane has no child labeled i, it contains an object ti. If ri = 0 then ti is in the skin membrane and there is no membrane with label i. Object representing the label of the current instruction (xip) is in the skin membrane.
We will have following rules in the skin membrane: 1. xj si → [isi]isixk for instruction j : (add(i), k, _), 2. xj ti → [iti]isixk for instruction j : (add(i), k, _), 3. xj ti → xlti for instruction j : (sub(i), k, l), 4. xj si → xj ↓i for instruction j : (sub(i), k, l),
For the membrane i: 5. xj → xkδ
For every add instruction there is just one rule applied in the simulation and for each sub instruction there is one or two instructions, depending on the register value. If ri > 0 then the instruction enters the membrane labeled i and dissolves it, decreasing the number of stacked membranes with label i. ⊔⊓ Example 4. Assume a register machine with two registers with values r1 = 2 and r2 = 0. The corresponding membrane configuration is [3[1[1t1]1s1]1s1t2xj ]3. If the current instruction is j : sub(1, k, l) then the only applicable is the rule 4 which results in the configuration [3[1[1t1]1s1xj ]1s1t2]3. Then the only applicable is the rule 5 which dissolves the membrane 1 resulting in the configuration [3[1t1]1s1]1s1t2xk]3.
For another example, consider instruction j : add(1, k, k). The increment is simulated by wrapping the membrane 1 to a new membrane created by the rule 1 with the resulting configuration [3[1[1[1t1]1s1]1s1]1s1t2xk]3.
This simulation is the most suitable for simulating the register machine because for incrementing the number of stacked membranes we just need to wrap the topmost membrane into a new membrane. This gained us constant time for executing one instruction, however the number of membranes remains linear on the sum of register values. The number of objects is number of instructions + 2 ∗ number of registers.
We have investigated the bridge between membrane systems and reaction systems for the sequential variant with active membranes. We have shown computational completeness by a simulation of a register machine. When using sets instead of multisets, the original definition of creating a membrane may seem obsolete. Therefore, we have proposed alternative definitions for membrane creation: inject-or-create and wrap-orcreate. In either case the resulting system has been shown to be universal.
As some simulations are not very effective, we have also proposed ways to improve the efficiency. For the simulation with original membrane creation we managed to reduce time needed for executing one instruction of the register machine from linear to logarithmic time. The wrap-or-create semantics is the most suitable for the simulation as for every instruction of the register machine only constant number of steps of the P system is needed.
The register value in the simulations is encoded in either unary or binary form. We propose other options to encode the register value as a tree structure of membranes and leave the construction of the simulation as a topic for further study.