A Kernel P System

A Kernel P System Marian Gheorghe1,2, Florentin Ipate2, and Ciprian Dragomir1 1Department of Computer Science University of Sheffield Portobello Street, Regent Court, Sheffield, S1 4DP, UK {m.gheorghe, c.dragomir}@sheffield.ac.uk 2Department of Computer Science University of Pitesti Str Targu din Vale, 1, Pitesti, Romania [email protected] Summary. A basic P system, called kernel P system (kP system for short), covering features of different P systems introduced and studied so far is defined and discussed. It is a relatively low level specification system aiming to cover features exhibited by most of the problems modelled so far using P system formalisms. A small set of rules and specific strategies to run the system step by step are presented. Some preliminary results regarding the relationships between kP systems and other classes of P systems, like neural-like P systems and P systems with active membranes, are presented. Examples illustrating the behaviour of kP systems or showing how a sorting algorithm is modelled with various classes of P systems are provided. Further developments of this class of P systems are finally briefly discussed. 1 Introduction Different variants of P systems have been used for specifying simple algorithms [4, 2], classes of NP-complete problems [7] and other various applications [5]. More specific classes of P systems have been recently considered for modelling various distributed algorithms and problems [9]. In many cases the specification of the system investigated requires features, constraints or type of behaviour which are not always provided by the model in its initial definition. It helps in many cases to have some flexibility with modelling approaches, especially in the early stages of modelling, as it might simplify the model, shorten associated processes and clarify more complex or unknown aspects of the system. The downside of this is the lack of a coherent and well-defined framework that allows us to analyse, verify and test this behaviour and simulate the system. In this respect we engage now on defining akernel P system (kP system, for short) that, at least for this stage, will be a low level specification language including the most used concepts from P systems. In a later stage its key features will be formally defined in an operational style and 154 M. Gheorghe, F. Ipate, C. Dragomir finally implemented within a model checker (SPIN [3], Maude [6]) and integrated into the P-lingua platform. We will be working with P systems having a graph-like structure (so called, tissue P systems) using a set of symbols, labels of membranes, rules of various types and various strategies to run them against the multiset of objects available in each region. The rules in each compartment will be of two types, (i) object processing rules which transform and transport objects between compartments or exchange objects between compartments and environment and (ii) system structure rules responsible for changing the system’s topology. Each rule has a guard, defined using activators and inhibitors in a more general way than in traditional P system classes. An execution strategy can now be specified individually, for each compartment, allowing for more complex rule selection and iteration procedures in addition to the classical maximal parallelism and sequential methods. We consider rewriting and communication rules based on promoters and inhibitors as they seem to be amongst the most flexible and general processing rules, and a special set of symport/antiport rules; additional features like membrane division, dissolution, bond creation and destruction are also considered. Two types of P systems, neural-like P systems and P systems with active membranes, are simulated by the newly introduced P systems. We analyse a specific case study based on a sorting algorithm which is described using the currently introduced model, kP systems, and some other formalisms, using electrical charges, states and labels. 2 kP Systems A kP system is a formal framework that uses some well-known features of existing P systems and includes some new elements and, more importantly, it offers a coherent view on integrating them into the same formalism. The key elements of a kP system will be formally defined in this section, namely objects, types of rules, internal structure of the system and strategies for running such systems. Some preliminary formal concepts describing the syntax of kP systems and an informal description of the way these systems are executed will be introduced. We consider that standard concepts like strings, multisets, rewriting rules, and computation are well-known concepts in P systems and indicate [11] as a comprehensive source of information in this respect. First we introduce the key concept of a compartment. Definition 1. Given a finite set, A, called alphabet, of elements, called objects, and a finite set, L, of elements, called labels, a compartment is a tuple C= (l, w0, Rσ), where l∈Lis the label of the compartment, w0is the initial multiset over Aand Rσdenotes the DNA code of C, which comprises the set of rules, denoted R, applied in this compartment and a regular expression, σ, over Lab(R), the labels of the rules of R. The precise format and the types of rules used in this context will be discussed in Section 2.1. A Kernel P System 155 Definition 2. Akernel P system of degree nis a tuple kΠ = (A, L, IO, µ, C1, . . . , Cn, i0), where Aand Lare, as in Definition 1, the alphabet and the set of labels, respectively; IO is a multiset of objects from A, called environment;µdefines the membrane structure, which is a graph, (V, E), where Vare vertices, V⊆L(the nodes are labels of these compartments), and Eedges; C1, . . . , Cnare the ncompartments of the system - the inner part of each compartment is called region, which is delimited by a membrane; the labels of the compartments are from L and initial multisets are over A;iois the output compartment where the result is obtained. As usual in P systems, the environment contains an arbitrary number of copies of each object. Each compartment is specified according to Definition 1. 2.1 kP System Rules The discussion below assumes that the rules introduced belong to the same compartment, Ci, labelled li. Each rule rmay have a guard g, in which case ris applicable when gis evaluated to true. Its generic form is r{g}. The guards are constructed according to certain criteria described below. Before presenting these criteria we introduce some notations. We consider multisets over A∪¯ A, where Aand ¯ Aare interpreted as promoters and inhibitors, respectively; ¯ A={¯a|a∈A}. For a multiset wover A∪¯ Aand an element afrom the same set we denote by #a(w) the number of a′s occurring in w. We also consider the set of well-known relational operators Rel ={<, ≤,= ,=,≥, >}. For a multiset w=an1 1. . . ank k,aj∈A∪¯ A, 1 ≤j≤k, and αj∈Rel, 1≤j≤k, we introduce the following notation w′=α1an1 1. . . αkank k;ajis not necessarily unique in wor w′(as it will transpire from the explanations below, this case may occur when the multiplicity of a symbol belongs to an interval); w′ is called multiset over A∪¯ Awith relational operators over Rel. If gis a guard defined according to the criteria below and pr, a predicate over this set of guards, then: •g=ϵmeans pr(ϵ) is always true, i.e., no condition is associated with the rule r; this guard is almost always ignored from the syntax of the rule; •gis a multiset over A∪¯ Awith relational operators over Rel, i.e., g= α1an1 1. . . αkank k, then pr(w) is true iff for z, the current multiset of Ci, we have, for every 1 ≤j≤k, either (i) if aj∈Athen #aj(z)αjnjholds, or (ii) if aj∈¯ A, i.e., aj= ¯a, a ∈A, then #a(z)αjnjdoes not hold; •g=w1|...|wp, i.e., gis a finite disjunction of multisets over A∪¯ Awith relational operators over Rel, then pr(w1|. . . |wp) is true iff there exists 1 ≤ j≤p, such that pr(wj) is true. 156 M. Gheorghe, F. Ipate, C. Dragomir We denote by FE(A∪¯ A), from Finite regular Expressions over A∪¯ Awith relational operators, the set of expressions defined above. When a compound guard, cg, referring to compartments liand ljis used, its generic format is cg =li.g1op lj.g2, where g1, g2are finite expressions referring to compartments liand lj, respectively; then, obviously, pr(cg) = pr(g1)op pr(g2), op ∈ {&,|}, where & stands for and and |for or, meaning that either both guards are true or at least one is true. Simpler forms, where one of the operands is missing, are also allowed as well as cg =ϵ. A compound guard defines a Boolean condition defined across the two compartments. Example 1. If the rule is r:ab →c{≤ a3≥b7= ¯c}, then this can be applied iff the current multiset consists of at most 3 a′s and at least 7 b′s and does not contain a single c(either none or more than 2 c′s are allowed). A rule can have one the following types: •(a) rewriting and communication rule: x→y{g}, where x∈A+,y∈A∗,g∈FE(A∪¯ A); the right hand side, y, has the form y= (a1, t1). . . (ah, th), where aj∈Aand tj∈L, 1 ≤j≤h, is an object and a target, i.e., the label of a compartment, respectively; the target, tj, must be either the label of the current compartment, li, (more often ignored) or of an existing neighbour of it ((li, tj)∈E) or an unspecified one, ∗; otherwise the rule is not applicable; if a target, tj, refers to a label that appears more than once then one of the involved compartments will be non-deterministically chosen; if tjis ∗then the object ajis sent to a neighbouring compartment arbitrarily chosen; •(b) input-output rule, is a form of symport/antiport rule: (x/y){g}, where x, y ∈A∗,g∈FE(A∪¯ A); xfrom the current region, li, is sent to the environment and yfrom the environment is brought into the current region; •(c) system structure rules; the following types are considered: – (c1) membrane division rule: []li→[]li1. . . []lih{g}, where g∈FE(A∪¯ A); the compartment liwill be replaced by hcompartments obtained from li, i.e., the content of them will coincide with that of li; their labels are li1, . . . , lih, respectively; all the links of liare inherited by each of the newly created compartments; – (c2) membrane dissolution rule: []li→λ{g}; the compartment liwill be destroyed together with its links; – (c3) link creation rule: []li; []lj→[]li−[]lj{cg}; the current compartment, li, is linked to ljand if more than one ljexists then one of them will be non-deterministically picked up; cg, called compound guard, describes an expression li.g1op lj.g2as defined above; – (c4) link destruction rule: []li−[]lj→[]li; []lj{cg}; is the opposite of link creation and means that compartments li, ljare disconnected; as usual, when more than a link, (li, lj)∈E, exists then only one is considered by this rule; cg is a compound guard. A Kernel P System 157 2.2 Regular Expressions and their Interpretation for kP Systems In kP Systems the way in which rules are executed is described using regular expressions (over the sets of labels of rules). This approach allows the usual behaviour of P systems - requiring the rewriting and communication, and input-output rules to be applied in a maximal parallel way and structural rules (e.g. membrane division and dissolution, creation and destruction of links) to be executed one per membrane - as well as other alternative or additional features to be expressed in a consistent and elegant manner. We first consider the set of labels of the rules, from the set R, in a given compartment, denoted by Lab(R). We can define regular expressions over this set, REG(Lab(R)). A regular expression σ∈REG(Lab(R)) is interpreted as follows •σ=ϵmeans no rule from the current compartment will be executed; •σ=r,r∈Lab(R), means the rule ris executed; •σ=αβ means first are executed rules designed by αand then those in β; •σ=α|βmeans either the rules designed by αor those by βare executed; often we use the notation defining sets where |is replaced by ,; •σ=γ∗means rules designed by γare executed in a maximal parallel way. Regular expressions allows the definition of various execution strategies, including well-known maximal parallelism (and also sequential) behaviour, but also to encode more subtle concepts like order relationships between rules, which introduce a form of sequential execution. Given the above introduced types of rules we can also specify in a more coherent way the fact that maximal parallelism imposes some constraints on the way the rules dealing with the system structure are handled; it is always the case that such rules are applied one per compartment and at the end of each step. Indeed, this assumption can be made in this case as the left hand side of any of the rules c1–c4 , does not contain any object, so they are applied only when there guards are satisfied. These cases are briefly analysed below. •Naturally, ∗is used to capture the maximal parallelism of a set of rules; for rules R, with Lab(R) = {r1, . . . , rk}, we mostly write either Lab(R)∗or {r1, . . . , rk}∗, instead of (r1|. . . |rk)∗. •In order to express the fact that maximal parallelism means that object processing rules are applied in a maximal parallel way and at the end only one of the system structure rules is applied, we first split R, the set of rules, into R1, containing all the object processing rules, and R2, with all the structure defining rules, associated with the current compartment; then given the convention introduced for the set of regular expressions over Lab(R), the above behaviour is expressed by Lab(R1)∗Lab(R2). •Now suppose that a certain order relationship exists, e.g. r1, r2> r3, r4, which means that when weak priority is applied, the first two rules are executed first, if possible, then the next two. If both are executed with maximal parallelism, this is described by {r1, r2}∗{r3, r4}∗. 158 M. Gheorghe, F. Ipate, C. Dragomir These regular expressions define the strategy of executing the rules of the current compartment and together with them they form the true DNA code of each compartment. Other ways of executing the rules of a compartment, like equal to, less than or greater than a given number of steps, can be also considered. The result of a computation will be the number of objects collected in the output compartment. For a kP systems kΠ, the set of all these numbers will be denoted by M(kΠ). 2.3 kP System Examples In this section we illustrate the newly introduced P system model with some examples. Example 2. Let us consider the following kP system with n= 4 compartments, kΠ1= (A, L, IO, µ, C1, . . . , C4,1), where A={a, b, c, p}, L={1,2,3}, IO contains an arbitrary number of objects over {b, c}, C1= (1, w1,0, Rσ 1), C2= (2, w2,0, Rσ 2), C3= (2, w3,0, Rσ 2), C4= (3, w4,0, Rσ 3), µis given by the following graph with edges (1,2),(1,3); (1,2) appears twice as n= 4 and there are two compartments, C2, C3, with label 2; w1,0=a3p,w2,0=p,w3,0=p,w4,0=λ, and Rσ 1is R1={r1:a→a(b, 2)(c, 3) {≥ p};r2:p→p;r3:p→λ},and σ1= Lab(R1)∗, Rσ 2is R2={r1: (b/c){≥ p};r2:p→p;r3:p→λ},and σ2=Lab(R2)∗, Rσ 3is R3=∅and σ3=Lab(R3)∗. Please note that we do not use targets for objects meant to stay in the current compartment (i.e. we have r1:a→a(b, 2)(c, 3) {≥ p}instead of r1:a→(a, 1)(b, 2)(c, 3) {≥ p}). In this example there are only rewriting and communication rules (all the rules, but r1from R2) and an input-output one (r1from R2); some rules have a guard, ≥p(pis a promoter), others do not have any and in each compartment the rules are applied in maximal parallel way in every step, as indicated by σj, 1 ≤j≤3. As two instances of the compartment labelled 2, C2, C3, appear in the system, when the rule r1from the first compartment is applied, the object bgoes nondeterministically to one of the two compartments labelled 2 as long as premains in compartment 1; object cgoes always to compartment labelled 3, C4. The initial configuration of kΠ1is M0= (a3p, p, p, λ). The only applicable rules are r1, r2and r3from C1and r2, r3from C2, C3. If r1, r2are chosen in C1 and r2in C2, C3, then a3pis rewritten by r1, r2in C1and pin C2, C3by r2; then three a′s stay in C1, three b’s go non-deterministically to C2, C3, three c’s go to compartment labelled 3, C4, and each pin C2, C3stays in its compartment. Let us assume that two of them go to C2and one to C3. Hence, the next configuration is M1= (a3p, b2p, bp, c3). If in the next step the same rules are applied identically in the first compartment, C1, and rules r1, r2are used in C2and r1, r3in C3, then A Kernel P System 159 the next configuration is M2= (a3p, b2c2p, bc, c6). If now r1, r3are used in C1, with r1used in the same way and r1, r3in C2(no rule is available in C3) then M3= (a3, b2c4, b2c, c9); this is a final configuration as there is no promoter to trigger a further step. Observation. If r1:a→a(b, 2)(c, 3) {≥ p}from C1is changed to r1:a→ a(b, 2)(c, ∗){≥ p}, then the three resulting c′s (obtained after applying r1to a3) go non-deterministically to any of the three neighbours of C1. Example 3. Let us reconsider the example above enriched with rules dealing with the system structure. First we will show how the system handles the multiplication of compartments with label 2, C2and C3, when a certain condition holds; we will consider the guard ≥b2≥p. In this case the new kP system, denoted kΠ2, will have the same structure and content as kΠ1except Rσ 2which is now defined as follows Rσ 2is R2=R(1) 2∪R(2) 2, where R(1) 2={r1: (b/c){≥ p};r2:p→p;r3:p→λ}, R(2) 2={r4: []2→[]2[]2{≥ b2≥p}} and σ2=Lab(R(1) 2)∗Lab(R(2) 2). We can notice that the regular expression σ2tells us that first the rewriting rules are applied in a maximal parallel manner and then one of system structure rules is chosen to be executed. If the system follows the same pathway as kΠ1then M2shows a different configuration given that in C2after applying R(1) 2in a maximal parallel manner, R(2) 2 is applied as indicated by σ2, when the guard of r4is true. The compartment C2 is divided into two compartments, C2,1, C2,2, with the same label 2 and appearing on positions 2 and 3 in the new configuration, M′ 2= (a3p, b2c2p, b2c2p, bc, c6); the new compartments labelled 2 are linked to compartment C1. In the next step both are divided as they contain the guard triggering the membrane division rule r4. The process will stop when either pwill be rewritten to λor b2stops coming. If we aim to either dissolve or disconnect a compartment labelled by 2 from compartment C1, once a certain condition is true, for instance b2c2pappears in it, then two more rules will be added to R(2) 2, namely r5: []2→λ{≥ b2≥c2≥p},r6: []2−[]1→[]2; []1{≥ b2≥c2≥p}. The same regular expression, σ2=Lab(R(1) 2)∗Lab(R(2) 2), is used, but in this case R(2) 2contains three elements and at most one is applied at each step, in every compartment with label 2. 3 Neural-like P Systems and P Systems with Active Membranes versus kP Systems In order to prove how powerful and expressive kP systems are, we will show how two of the most used variants of P systems are simulated by kP system. More precisely, we will show how neural-like P systems and P systems with active membranes are simulated by some reduced versions of kP systems. 160 M. Gheorghe, F. Ipate, C. Dragomir Definition 3. Aneural-like P system (tissue P system with states) of degree nis a construct Π= (O, σ1, ...σn, syn, i0)([10], p. 249), where: •Ois a finite, non-empty set of objects, the alphabet; •σi= (Qi, si,0, wi,0, Ri),1≤i≤n, represents a cell and –Qiis the finite set of states of cell σi; –si,0∈Qiis the initial state; –wi,0∈O∗is the initial multiset of objects contained in cell σi; –Riis a finite set of rewriting and communication rules, of the form sw → s′xygozout; when such a rule is applied, xwill replace win cell σi, the objects from ywill be sent to neighbouring cells, according to the transmission mode (see th next Observation) and the objects from zwill be sent out into the environment; cell σiwill move from state sto s′; •syn ⊆ {1, ..., n}×{1, ..., n}, the connections between cells, synapses; •i0is the output cell. Observations. 1. For such systems, three processing modes are considered, called “max”, “min”, “par”, and three transmission modes, namely “one”, “repl”, “spread”. For formal definitions and other details we refer to [10]. 2. We denote by simple neural-like P systems the class of P systems given by Definition 3, with rewriting and communication rules sw →s′x(a1, t1)· · · (ap, tp), where th, 1 ≤h≤p, denotes the target cell (σh), and processing mode “max”, transmission mode defined by the target indications mentioned in each rule. Notation. For a given P system, Π, the set of numbers computed by Πwill be denoted by M(Π). Theorem 1. If Πis neural-like P system of degree n, then there is a kP system, Π′, of degree nand using only rules of type (a), rewriting and communication rules, simulating Πand such that M(Π′)⊆M(Π)∪ {2}. Proof. Let Πbe a simple neural-like P systems of degree n, as defined above. We construct Π′as follows: Π′= (A, L, IO, µ, C1, ..., Cn) where: •A=O∪(∪1≤i≤nQi)∪ {γ};γis a new symbol neither in Onor in ∪1≤i≤nQi; •L={1, ..., n};IO =∅; •µ=syn; •Ci= (i, w′ i,0, R′σ i),1≤i≤n; and –w′ i,0=γ, 1≤i≤n; –R′ icontains the following rules: 1. γ→si,0twi,0, where si,0, wi,0are the initial state and initial multiset, respectively, associated with cell σi, and t∈Q(i) si,0. For s∈Qi, denote by Q(i) s={t|t∈Qi, sx →ty ∈Ri}; i.e., Q(i) sgives, when the cell σi is in state s, all the states where σican move to. In the first step, in A Kernel P System 161 compartment Ci, a rule γ→si,0twi,0is applied and the current multiset becomes w′ i=si,0wi,0. 2. For each pair (s, t), t ∈Q(i) s, there are rules sxi→tyi∈Ri,1≤i≤p(∗). If there are no rules in Rifrom sto tthen another pair is considered. For the above rules, the following rules are considered in R′ i: xi→yi{=s=t}, 1 ≤i≤p, and st →tq {≥ x1|...| ≥ xp},q∈Q(i) t (∗∗) In the above guards the notation ≥xi, if xi=ai,1. . . ai,li, denotes ≥ai,1. . . ≥ai,li. The rules (∗∗) make use of guards; the first prules are applied iff the current multiset contains one sand one t, whereas the last one is applicable iff at least one or more of the occurrences of one of the multisets xi, 1 ≤i≤p, is included in the current multiset. Clearly, in state sonly the rules (∗) of Πare applicable for this P system, depending on the availability of the multisets occurring on the left hand side of them; the next state Πis moving to is t. Similarly, in Π′only the rules denoted by (∗∗) are applicable; the rule st →tq {≥ x1|...| ≥ xp} is applied once whereas the first prules are applied as many times as their corresponding (∗) rules are applied. If the set Q(i) tused in st →tq {≥ x1|...| ≥ xp}of (∗∗) is empty, i.e., there are no rules from state t, then the rule is replaced by st →λ. When Q(i) si,0=∅then the rule γ→wi,0is introduced in R′ i. At any moment the component Ciof the kP system Π′contains a multiset which is the multiset of σiaugmented by the current state of σi,s, and one of the next states, t, if it exists. The process will stop in component Ciof Π′when no pair of rules of type (∗∗) is applicable, which means no sxi→tyirule is applicable in state s. The multiset M(Π′) contains M(Π) and maybe two states s, t occurring in the last step of the computation. Hence M(Π′)⊆M(Π)∪ {2}.⊓⊔ Comments. 1. The above simulation can be assessed with respect to number of compartments, objects and rules as well as the computation steps. 2. When rules sw →txygo are used in the “spread” mode, this means that any a∈Ooccurring in ymay go to any of the neighbours. In this case if y=y1ay2 then for each such a∈O, the rules of R′ icorresponding to sw →txygo, denoted (∗∗) above, will show w→xy {=s=t}replaced by w→xy1(a, j)y2{=s=t}, where jthe label of one of the neighbours of the current compartment. For “one” mode all a′s in ywill point to the same target, j, for all neighbours of the compartment i. 3. The transmission replicative mode - when a symbol is sent to all the neighbours, can also be simulated. Indeed if j1,· · · , jhare the neighbours of i, then w→ xy1(a, j)y2is transformed into w→xy1(a, j1)· · · (a, jh)y2for each a. 168 M. Gheorghe, F. Ipate, C. Dragomir r8:y2[]0 j→[x1]+ j,1≤j≤n; r9:y2[]+ j→[x1]0 j,1≤j≤n; where i∈ {0,+}; and the order relationship r1, r2, r4, r5, r6, r7, r8, r9> r3. M/S []1[]2[]3[]4[]5[]6[]aux 0 [a3x1]0[a6x1]+[a9x1]0[a5x1]+[a7x1]0[a8x1]+[ ]0 1 [a3b6x2]0[x2]+[a9b5x2]0[x2]+[a7b8x2]0[x2]+[ ]0 2 [a6]+[a3y1]0[a9y1]+[a5y1]0[a8y1]+[a7y1]0[y1]0 3 [a6]+[a3b9y2]0[y2]+[a5b8y2]0[y2]+[a7y2]0[y2]0 4 [a6x1]0[a9x1]+[a3x1]0[a8x1]+[a5x1]0[a7x1]+[ ]0 5 [a6b9x2]0[x2]+[a3b8x2]0[x2]+[a5b7x2]0[x2]+[ ]0 There are no additional requirements in the case where n= 2k+ 1, however we always entail an extra auxiliary membrane to enable out communication of the n−th membrane, therefore allowing it to switch polarity. A similar implementation of the static sorting algorithm can be obtained by using P systems with labels on membranes. As illustrated in [1], we can encode electrical charges in strings of the membrane labels, in order to differentiate between the two necessary states. For each membrane hiwe synthesise its complementary label h′ i, which is changed to by a communication rule. We leave this as an exercise to the reader. A number of (preliminary) conclusions can be drawn from the above case study: •kP systems are conceptually closer to tissue P systems than cell-like P systems; in our case studies, this is reflected by the similarity between the specifications using kP systems and tissue P systems, respectively. On the other hand, the model realized using the cell-like P system variant is significantly more complex. •In terms of complexity, the three implementations are roughly equivalent. The kP system executes in each step one more rule then the P system with states; this rule is either r2or r3(dealing with p). On the other hand, the number of rules applied in each compartment for every step by cell-like P systems is similar to the case of kP systems. 5 Conclusions The kP system introduced in this work represents a low level specification language. Its syntax and informal semantics and some examples have been introduced and discussed. A case study based around a simple sorting algorithm has allowed us to compare different specifications of this using various types of P systems. In the next stage formal semantics will be defined and an implementation using model checkers (SPIN, Maude) is also expected. Several extensions can be considered for kP systems that may lead to a more flexible and higher level specification language. A first set of extensions refer to ways of defining objects, rules and compartments A Kernel P System 169 using indexes over some specified domains. Modules can also be introduced using a syntactic approach, rather than considering additional semantic features [8]. In order to prove the expressive power of kP systems, a more systematic study of simulating important classes of P systems with kP systems will be produced in a forthcoming paper. Acknowledgement. The work of MG and FI was partially supported by project MuVet, Romanian National Authority for Scientific Research (CNCS – UEFISCDI) grant number PN-II-ID-PCE-2011-3-0688. References 1. A. Alhazov, L. Pan, Gh. P˘aun, Trading Polarizations for Labels in P Systems with Active Membranes, Acta Informatica, 41, 111-144, 2004. 2. A. Alhazov, D. Sburlan, Static Sorting P Systems. In [5], 215 – 252, 2006. 3. M. Ben-Ari, Principles of the SPIN Model Checker, Springer, 2008. 4. R. Ceterchi, C. Mart´ın-Vide, P Systems with Communication for Static Sorting. In Pre-Proceedings of Brainstorming Week on Membrane Computing, Tarragona, February 2003, M. Cavaliere, C. Mart´ın-Vide, Gh. P˘aun, eds., Technical Report no 26, Rovira i Virgili Univ., Tarragona, 101–117, 2003. 5. G. Ciobanu, Gh. P˘aun, M. J. P´erez-Jim´enez, eds., Applications of Membrane Computing, Springer, 2006. 6. M. Clavel, F.J. Dur´an, S. Eker, P. Lincoln, N. Mart´ı-Oliet, J. Meseguer, Maude: Specification and Programming in Rewriting Logic, Theoretical Computer Science, 285, 187 – 243, 2002. 7. D. D´ıaz-Pernil, M. A. Guti´errez-Naranjo, M. J. P´erez-Jim´enez, A Uniform Family of Tissue P Systems with Cell Division Solving 3-COL in a Linear Time, Theoretical Computer Science, 404, 76 – 87, 2008. 8. M. Gheorghe, V. Manca, F.J. Romero-Campero, Deterministic and Stochastic P Ssytems for Modelling Cellular Processes, Natural Computing, 9, 457–473, 2010. 9. R. Nicolescu, M. J. Dinneen, Y.-B. Kim, Structured Modelling with Hyperdag P Systems: Part A. In Membrane Computing, Seventh Brainstorming Week, BWMC 2009, Sevilla, Spain, February 2009, R. Guti´errez-Escudero, M. A Guti´errez-Naranjo, Gh. P˘aun, I. P´erez-Hurtado, eds., Universidad de Sevilla, 85 – 107, 2009. 10. Gh. P˘aun, Membrane Computing: An Introduction, Springer, 2002. 11. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds., Handbook of Membrane Computing, Oxford University Press, 2010.