# Research on P System with Chain Structure and Application and  Simulation in Arithmetic Operation

Authors: Jing Luan; Zhong Yao
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

Considering the advantages of distribution and maximum parallelism of membrane computing and availability of discrete Morse theory to deal with discrete structure, in this paper, combining discrete Morse theory and membrane computing, a novel membrane structure—P system with chain structure, is proposed, which is constructed on the basis of discrete gradient vector path of the discrete Morse theory. At the theoretical level, due to its unique chain structure, compared with traditional P system, its structure, object, and rule are described in details. In the practical aspect, a specific application example, P chain system for arithmetic operation, is presented to demonstrate the superiority, computational efficiency, and ability of P system with chain structure. Moreover, a simulation system of arithmetic operations based on P chain system is designed, giving a visual display of the implementation of P chain system for arithmetic operation, and verifying the feasibility and effectiveness of P chain system.


---

## Body

## 1. Introduction

Membrane computing is a new computational model proposed by Romanian scientist Păun in 1998, due to being introduced by Păun at the first time, it is also called P system [1]. Membrane computing abstracts cell as the computational unit, permitting every computational unit to calculate dependently and the whole system to operate in the way of maximum parallelism, whose computational efficiency has been improved obviously [2–5]. It has been proved that the computation capacity of membrane computing is equivalent with that of turing machines, so due to its strong parallel computing power it has been the highlight of the recent study.Morse theory [6] is a useful tool in differential topology, applied for investigating the topology of smooth manifolds, particular for computer graphics, having been the focus of the research. Forman [7] extended it to the discrete aspect, which provides an effective tool to describe the topology of discrete object, such as simplex and simplicial complex and plays a vital role in pure mathematics and applied mathematics. Concepts in discrete Morse theory, such as simplex [8], discrete gradient vector path and so on, provide a useful tool to research the topology of discrete structure.Generally, the structure of P system is abstracted as the nested structure of the cell wall and organelle, so it is a kind of nested and hierarchical structure. Of course, there are many other structures, such as reticular formation of neural network. Up to now, there are three main P systems, cell-like P system, tissue-like P system and neural P system [3], and the study of cell-like P system has been well-developed. In literature [4], Păun pointed out that the focus of the next stage of membrane computing study was the nonhierarchical arrangement of membranes. In literature [9], the author has proposed a P system based on simplicial complexes, which is an innovative try in the aspect of nonhierarchical membrane structure. Inspired from this, in this paper, a P system with chain structure is introduced, which combines membrane computing with discrete Morse theory and constructs a P system based on the discrete gradient vector path, forming a new kind of nonhierarchical membrane structure—P chain system. To try to arrange a novel nonhierarchical structure of P system not only makes a contribution to knowledge but also makes a clear methodological contribution.The organization of the reminder in this paper is described as follows: Section2 is the part of theoretical discussion, reviewing theories and properties of discrete Morse theory and P system, which are the foundation of P system with chain structure, and then giving the specific description of structure, object, and rule of P chain system. In Section 3, a practical application of P chain system, P chain system for arithmetic operation, is proposed, displaying +,-,*,/ four kinds of P chain systems. In Section 4, by a computer simulation, the specific implementation of P chain system for arithmetic operation is demonstrated, showing the computational efficiency and power of P system with chain structure. In Section 5, the summary and prospect are included.


## 2. P System with Chain Structure

### 2.1. Foundation of P System with Chain Structure

#### 2.1.1. Discrete Morse Theory

Here are some core definitions in discrete Morse theory, which are also essentials in this paper [6–9].Definition 1 (Q-simplex).
Assuming thata0,a1,a2,…,aq are q+1 points which cover the widest position in n-dimensional Euclidean space and q≤n, that is to say, vectors e1=a1-a0, e2=a2-a0,…,eq=aq-a0 are linearly independent relationship with each other, then defining x=λ0a0+λ1a1+⋯+λqaq, written as x=∑i=0kλiαi, and real number λ0,…,λq satisfying two factors: (1) ∑i=0qλi=1; (2) λ0,λ1,…,λq≥0, the set of x in En is called q-simplex, marked as s_q, while a0,a1,a2,…,aq are called vertices of the simplex. A simplex is uniquely denoted by its vertices; therefore it can be expressed as [a0,a1,a2,…,aq] or a0a1a2⋯aq simply.Definition 2 (simplex with orientation).
For aq-simplex s_q, there are (q+1)! permutations of different sequences for its q+1 vertices a0,a1,a2,…,aq; when q>0, there are two kinds of permutations; any two permutations of the same kind differ in even commutations, while any two permutations in different group differ in odd commutations. These two kinds are called two orientations of s_q. The simplex which has been given an orientation is called simplex with orientation, one denoted as sq and the other as -sq.Definition 3 (Q-chain).
Suppose a fundamental constituent{siq} of n-complex K, for an integer gi, there is gisiq=(-gi)(-siq), and a linear combination with integer coefficient xq=g1s1q+g2s2q+⋯+gaqsaqq is called q-chain of K.Definition 4 (discrete gradient vector field).
For the gradient vector fieldV on a n-complex K, it is a series of ordered pair sets denoted as {α(p),β(P+1)} and subjected to (1) α≺β, (2) each simplex of K belongs to one pair in V at most. Specifically, a gradient vector field is called discrete gradient vector field if and only if there is no nontrivial closed V-path on it, which is an alternating sequence of simplexes α0(p),β0(p+1),…,αr(p),βr(p+1),αr+1(p), where αi(p)≺βi(p+1) and {αi(p)≺βi(p+1)}∈V.


#### 2.1.2. P System Theory

Membrane computing is a novel computational model abstracted from biochemical reactions in living cells, whose merit is internal maximum parallelism. The essential components of P system are membrane structure, objects, and rules. The formalization definition of P system is shown as follows:(1)∏=O,T,C,u,w1,…,wm,R1,ρ1,…,Rm,ρm.HereO is the alphabet, representing the object; T is the output alphabet and T∈O; C is the catalyst and C∈O-T; u is the set of membranes; wi is the object multisets, i is the membrane label; Ri is the set of evolutionary rules, some rules are applied to reflect the chemical reactions, such as rewriting rules, and others are employed to simulate biological processes, such as communication rules, and ρi is the priority set of these rules.


### 2.2. Description of the P Chain System

#### 2.2.1. Definitions and Properties of P Chain System

Definition 5 (P system with chain structure).
Generalized P system with chain structure is written asXp=g1s1p+g2s2p+⋯+gapsapp, where gi is integer and |gi| represents the number of the membranes. Additionally, if ∀gi>0, XP represents positive generalized P system with chain structure, especially if ∀gi=1, XP denotes positive standard P chain system. Moreover, if ∀gi<0, XP represents negative generalized P chain system, particularly if ∀gi=-1, xp denotes negative standard P chain system. Furthermore, if ∃gi>0 or ∃gi<0, XP represents multiply generalized P chain system, especially if ∃gi=1 or ∃gi=-1, XP denotes multiply standard P chain system.Generally, what we call P system with chain structure is referred to the standard P chain system. Here is an example for the above definition. There is a complexA1B1C1D1-A2B2C2D2 in Figure 1(a), and 0-simplex are these vertices A1, B1, C1, D1, A2, B2, C2, D2, 1-simplex are these segments A1B1, C1D1, A2B2, C2D2, …, 2-simplex are these surfaces A1B1C1,A2B2C2,…, 3-simplex are these bodies B2-A1B1C1, A1-A2B2D2 and so on. There is a discrete gradient vector path A2→A2A1→ A1→A1B1→ B1→B1B2→ B2→B2C2→ C2→C2C1 →C1 on the 3-complex, composed by S0={A2,A1,B1,B2,C2,C1} and S1={A2A1,A1B1,B1B2,B2C2,C2C1}, so there are 0-chain A2+A1+B1+ B2+C2+C1 whose units come from S0 and 1-chain A2A1+A1B1+B1B2+B2C2+C2C1 whose units belong to S1. And then membranes from 0-chain or from 1-chain can compose a P system with chain structure. A2+A1+B1+B2+C2+C1 is an example of positive standard P chain system. 5A2A1+(-A1B1)+B1B2+(-3B2C2)+C2C1 can be called multiply generalized P chain system shown in Figure 1(b), where two-way arrow represents the repeated appearance of membrane, figure denotes the number of repeated appearance of its front membrane, that is to say, a1 appears 5 times and a3 3 times, usually 1 is omitted.The structure of P chain system.
(a)
ComplexA1B1C1D1-D2A2B2C2
(b)
P chain system based on discrete gradient vector path A2A1→A1B1→B1B2→B2C2→C2C1Property 1 (oriented property of P chain system).
There are three orientations of P chain system due to the orientation of simplex. What we entitle as P chain system with the same direction is that all the membranes are the same orientation, specifically in order to determine the direction of the P chain system, we need to predefine the orientation of complex, that is to say, if we stipulate the positive surfaceSq as positive, all the membranes from positive simplex of {Sq} form P chain system with positive orientation, marked by “+”, its membrane called positive membrane. On the contrary, all the membranes from the negative simplex of {-Sq} constitute the P chain system with negative orientation, marked by “−”, corresponding membrane called negative membrane. Moreover, if there are membranes from positive simplex or negative simplex at the same time in a P chain system, it is called P chain system with multiply orientation, marked by “×,” that is to say, in the P chain system with multiply orientation there are both positive membranes and negative membranes.Take the P chain systemA2A1→A1B1→B1B2→B2C2→C2C1 in Figure 1 for example. If we define clocklike orientation as the positive direction, P chain system A2A1→A1B1→B1B2→B2C2→C2C1 is positive one, and P chain system A1A2→B1A1→B2B1→C2B2→C1C2 is with negative orientation, while P chain system A2A1→B1A1→B1B2→B2C2→C1C2 is the example of multiply orientation.Property 2 (additive property of P chain system).
Supposing thatxq=g1s1q+g2s2q+⋯+gaqsaqq and yq=h1s1q+h2s2q+⋯+haqsaqq are any two q-chain, their addition xq+yq=(g1+h1)s1q+(g2+h2)s2q +⋯+(gaq+haq)saqq is also a q-chain. For the addition, all the q-chain of complex K are a free Abelian group, which is called q-chain group of K.Property 3 (precursory and subsequent relationships between adjacent membranes in P chain system).
Because P chain system is based on a discrete gradient vector path, the order of membranes is determined; that is, for a given P system with chain structure, the relationship between adjacent membranes is precursor or subsequent. For a P chain systemxp=r1α1p+r2α2p+⋯+rnαnp, where ri is integer and i=1,…,n, except the first membrane, usually the input membrane, for each membrane αip where i=2,…,n, its ahead membrane αi-1p is called its precursor; the relationship between αi-1p and αip is entitled as precursory relationship. Moreover, except for the last membrane, usually the output membrane, for arbitrary membrane αip, where i=1,…,(n-1), its back membrane αi+1p is called its subsequence; the relationship between αip and αi+1p is entitled as subsequent relationship.The algorithm for constructing the P system with chain structure is shown in Algorithm1.Algorithm 1:Construction algorithm of P system with chain structure.
INPUT: discrete Morse function M, the number of the membranes in P chain system N
OUTPUT: P system with chain structure
(1) Find out a discrete gradient vector path from the given discrete Morse functionM by the algorithm proposed in
literature [10];
(2) Find out setss_q consisted by all the q-simplex and s_q-1 consisted by all the (q-1)-simplex from the discrete gradient vector
path, noting that s_q and s_q-1 are ordered sets, ordered by the sequence of simplexes located in the discrete gradient
vector path;
(3) According to the number of membranesN in the P chain system, choosing adjacent N simplexes from s_q or s_q-1 as
membranes in the P chain system, constituting q-dimension or (q-1)-dimension P system with chain structure.


#### 2.2.2. Description of Structure, Object, and Rule of P Chain System

For the structure of P chain system, we know that it is nonhierarchical, specifically if it is a chain structure based on discrete gradient vector path, while for the object, it is similar with the former P system, which is denoted by multisets, meaning thatw=a1M(a1)a2M(a2)⋯anM(an) is used to represent objects of each membrane. But considering the oriented property of P chain system, the membrane is divided into positive and negative one, so objects in membrane with different orientations are different too; for example, supporting that object in positive membrane is marked as a, then object in negative membrane is marked as a′ correspondingly. a and a′ are antimatter, meaning that they cannot coexist; when they encounter each other, they will counteract immediately. This is similar with positive and negative spikes in spiking neural P system, where rule αα′→λ makes their coexistence impossible.Based on the rules of former P system, combining the particularities of P system with chain structure, there are three main rules of P chain system: rewriting rules, communication rules, and forgetting rules.Rewriting rule is with the form ofu→v, where u and v, from the alphabet O, are the objects which represent the multisets, and this rule can be used in membrane a when and only when the object set w in a satisfies w⊇u. Rewriting rules are used to control the type and number of objects in membrane. Here are some target indications used to manage the movement of objects. They include tar1={here,out,in}, where “here” indicates that object remains in the membrane, “out” denotes that object leaves the membrane into its subsequence, and “in” shows that object is sent out to its precursor. So rewriting rule with target indication is formed as u→v, where u is a string representing multisets of objects from a given set O, and v is a string over O*  {here,out,in}. Usually they are formed as (a,tar), where a is the object from O and tar is here (usually omitted) or in or out. For example, P chain system xp=r1α1p+r2α2p+r3α3p+r4α4p; there are object a3b2c4 and rule a2bc3→a2bc(da,out)(ca,in) in membrane a2; the result of the execution of the rule is to produce 4a,1b,2c,1d, where 1d and 1a will be sent into subsequence a3 and 1c and 1a will be sent into precursor a1, eventually remaining a3b2c2 in membrane a2.Communication rules are used to manage the communication across the membranes, including symport rules and antiport rules. Here another target indicationtar2={pre,sub} is introduced, where “pre” indicates that which move to the precursor of the membrane and “sub” denotes that which move to its subsequence. So in communication rules, target indication is shown in pair, formed as (tar1,tar2), where tar1={here,out,in} and tar2={pre,sub} and where tar2 can be omitted, meaning that objects will be sent into the precursor or subsequence randomly. In a P chain system where the structure is determined, defining that the membrane where rule resides is αip, its precursor is αi-1p, and its subsequence is αi+1p. Symport rules, formed as (u,in) or (u,(in,pre)) or (u,(in,sub)), express that object u from membrane αi-1p or membrane αi+1p is sent into membrane αip, “pre” or “sub” specifying the source of object u. Also there is the form of (u,out) or (u,(out,pre)) or (u,(out,sub)), which means that object u from membrane αip is sent out into membrane αi-1p or membrane αi+1p randomly or determined by the target “pre” or “sub”. Antiport rules is formed as (u,out;v,in) or (u,(out,tar2);v,(in,tar2)), where (u,out;v,in) means that object u from membrane αip is sent out into membrane αi-1p or membrane αi+1p randomly, at the same time, object v from the membrane αi-1p or membrane αi+1p is sent into membrane αip, while rule (u,(out,tar2);v,(in,tar2)) elaborates the specific precursor and subsequence. In fact, the target indication (tar1,tar2) can be simplified as tar1tar2, for example, symport rule (u,(out,sub)) in membrane αip can be expressed as (u,outαi+1p), in the same way, antiport rule (u,(out,tar2);v,(in,tar2)) can be shown as (u,outαi+1p;v,inαi-1p), which means that object v from precursory membrane αi-1p is sent into membrane αip, at the same time object u from membrane αip is sent out into subsequent membrane αi+1p.Forgetting rule is defined as the form ofu→λ, where u is object over alphabet O which is used to represent multisets, and λ is null. The function of forgetting rule is to disappear some certain objects in membrane. A typical example of forgetting rule is objects a,a′ which are antimatter in membranes with different orientation, when they encounter with each other, they will counteract immediately, resulting from the execution of rule aa′→λ. In most situations, forgetting rule aa′→λ does not appear explicitly, but is defaulted to execute with the highest priority. Note that when execute this rule, if there are object a or a′ in membrane where the rule resides, its objects a or a′ will be used at first, if there is no object a or a′, supporting that there are enough object a or a′ in environment can be used to counteract the antimatter.


### 2.3. Formalization Definition of P Chain System

The formalization definition of standard P system with chain structure is described as followed:(2)∏=O,T,C,u,σ0,σ1,…,σm,syn,in,out.(1)
Ois the alphabet, and the element from O is called object;(2)
T is output alphabet, and T∈O;(3)
C is catalyst (C∈O-T); the element of C is unchanged during the evolutionary process of system; that is to say, the char of C does not disappear and there is no new char generated, but its participation is necessary for some certain rules to execute;(4)
u is the set of membrane structures, each membrane and its enclosed area are expressed as label set H, H={1,2,…,m};(5)
σ1,…,σm denote that there are m membranes with chain structure σ1,…,σm, and membrane σi is represented as σi=(ni,Ri), 0≤i≤m, where
①
ni≥0 denotes the number of objects of membrane σi at the beginning of calculation;②
Ri shows the limited set of rules in membrane σi, there are three main forms.
(i)
Rewriting rules are showed asu→v, where u from the alphabet O represents the multisets; v is the string over set O*{here,out,in}, written as (a,tar), where a is the object from O and tar is here (usually omitted), out or in.(ii)
Communication Rules include symport rules and antiport rules. Symport rules are formed as(u,(tar1,tar2)), and antiport rules are showed as (u,(tar1,tar2);v,(tar1,tar2)), where u,v are the objects of alphabet O representing the multisets, and tar1={here,out,in}, tar2={pre,sub}, tar1 is used to control the direction of object in or out of the membrane, and tar2 explains the object will be sent into which membrane.(iii)
Forgetting Rules are formed asu→λ, where u is the object over O representing the multisets, and λ represents null. The execution of forgetting rules makes the number of objects in membrane less.(6)
syn={1,2,…,m} is used to show the relationship among membranes in P chain system, for each 1≤i≤m, there is σ1→σ2→⋯→σm;(7)
in,out∈{1,2,…,m} denote the input and output membranes.


## 2.1. Foundation of P System with Chain Structure

### 2.1.1. Discrete Morse Theory

Here are some core definitions in discrete Morse theory, which are also essentials in this paper [6–9].Definition 1 (Q-simplex).
Assuming thata0,a1,a2,…,aq are q+1 points which cover the widest position in n-dimensional Euclidean space and q≤n, that is to say, vectors e1=a1-a0, e2=a2-a0,…,eq=aq-a0 are linearly independent relationship with each other, then defining x=λ0a0+λ1a1+⋯+λqaq, written as x=∑i=0kλiαi, and real number λ0,…,λq satisfying two factors: (1) ∑i=0qλi=1; (2) λ0,λ1,…,λq≥0, the set of x in En is called q-simplex, marked as s_q, while a0,a1,a2,…,aq are called vertices of the simplex. A simplex is uniquely denoted by its vertices; therefore it can be expressed as [a0,a1,a2,…,aq] or a0a1a2⋯aq simply.Definition 2 (simplex with orientation).
For aq-simplex s_q, there are (q+1)! permutations of different sequences for its q+1 vertices a0,a1,a2,…,aq; when q>0, there are two kinds of permutations; any two permutations of the same kind differ in even commutations, while any two permutations in different group differ in odd commutations. These two kinds are called two orientations of s_q. The simplex which has been given an orientation is called simplex with orientation, one denoted as sq and the other as -sq.Definition 3 (Q-chain).
Suppose a fundamental constituent{siq} of n-complex K, for an integer gi, there is gisiq=(-gi)(-siq), and a linear combination with integer coefficient xq=g1s1q+g2s2q+⋯+gaqsaqq is called q-chain of K.Definition 4 (discrete gradient vector field).
For the gradient vector fieldV on a n-complex K, it is a series of ordered pair sets denoted as {α(p),β(P+1)} and subjected to (1) α≺β, (2) each simplex of K belongs to one pair in V at most. Specifically, a gradient vector field is called discrete gradient vector field if and only if there is no nontrivial closed V-path on it, which is an alternating sequence of simplexes α0(p),β0(p+1),…,αr(p),βr(p+1),αr+1(p), where αi(p)≺βi(p+1) and {αi(p)≺βi(p+1)}∈V.


### 2.1.2. P System Theory

Membrane computing is a novel computational model abstracted from biochemical reactions in living cells, whose merit is internal maximum parallelism. The essential components of P system are membrane structure, objects, and rules. The formalization definition of P system is shown as follows:(1)∏=O,T,C,u,w1,…,wm,R1,ρ1,…,Rm,ρm.HereO is the alphabet, representing the object; T is the output alphabet and T∈O; C is the catalyst and C∈O-T; u is the set of membranes; wi is the object multisets, i is the membrane label; Ri is the set of evolutionary rules, some rules are applied to reflect the chemical reactions, such as rewriting rules, and others are employed to simulate biological processes, such as communication rules, and ρi is the priority set of these rules.


## 2.1.1. Discrete Morse Theory

Here are some core definitions in discrete Morse theory, which are also essentials in this paper [6–9].Definition 1 (Q-simplex).
Assuming thata0,a1,a2,…,aq are q+1 points which cover the widest position in n-dimensional Euclidean space and q≤n, that is to say, vectors e1=a1-a0, e2=a2-a0,…,eq=aq-a0 are linearly independent relationship with each other, then defining x=λ0a0+λ1a1+⋯+λqaq, written as x=∑i=0kλiαi, and real number λ0,…,λq satisfying two factors: (1) ∑i=0qλi=1; (2) λ0,λ1,…,λq≥0, the set of x in En is called q-simplex, marked as s_q, while a0,a1,a2,…,aq are called vertices of the simplex. A simplex is uniquely denoted by its vertices; therefore it can be expressed as [a0,a1,a2,…,aq] or a0a1a2⋯aq simply.Definition 2 (simplex with orientation).
For aq-simplex s_q, there are (q+1)! permutations of different sequences for its q+1 vertices a0,a1,a2,…,aq; when q>0, there are two kinds of permutations; any two permutations of the same kind differ in even commutations, while any two permutations in different group differ in odd commutations. These two kinds are called two orientations of s_q. The simplex which has been given an orientation is called simplex with orientation, one denoted as sq and the other as -sq.Definition 3 (Q-chain).
Suppose a fundamental constituent{siq} of n-complex K, for an integer gi, there is gisiq=(-gi)(-siq), and a linear combination with integer coefficient xq=g1s1q+g2s2q+⋯+gaqsaqq is called q-chain of K.Definition 4 (discrete gradient vector field).
For the gradient vector fieldV on a n-complex K, it is a series of ordered pair sets denoted as {α(p),β(P+1)} and subjected to (1) α≺β, (2) each simplex of K belongs to one pair in V at most. Specifically, a gradient vector field is called discrete gradient vector field if and only if there is no nontrivial closed V-path on it, which is an alternating sequence of simplexes α0(p),β0(p+1),…,αr(p),βr(p+1),αr+1(p), where αi(p)≺βi(p+1) and {αi(p)≺βi(p+1)}∈V.


## 2.1.2. P System Theory

Membrane computing is a novel computational model abstracted from biochemical reactions in living cells, whose merit is internal maximum parallelism. The essential components of P system are membrane structure, objects, and rules. The formalization definition of P system is shown as follows:(1)∏=O,T,C,u,w1,…,wm,R1,ρ1,…,Rm,ρm.HereO is the alphabet, representing the object; T is the output alphabet and T∈O; C is the catalyst and C∈O-T; u is the set of membranes; wi is the object multisets, i is the membrane label; Ri is the set of evolutionary rules, some rules are applied to reflect the chemical reactions, such as rewriting rules, and others are employed to simulate biological processes, such as communication rules, and ρi is the priority set of these rules.


## 2.2. Description of the P Chain System

### 2.2.1. Definitions and Properties of P Chain System

Definition 5 (P system with chain structure).
Generalized P system with chain structure is written asXp=g1s1p+g2s2p+⋯+gapsapp, where gi is integer and |gi| represents the number of the membranes. Additionally, if ∀gi>0, XP represents positive generalized P system with chain structure, especially if ∀gi=1, XP denotes positive standard P chain system. Moreover, if ∀gi<0, XP represents negative generalized P chain system, particularly if ∀gi=-1, xp denotes negative standard P chain system. Furthermore, if ∃gi>0 or ∃gi<0, XP represents multiply generalized P chain system, especially if ∃gi=1 or ∃gi=-1, XP denotes multiply standard P chain system.Generally, what we call P system with chain structure is referred to the standard P chain system. Here is an example for the above definition. There is a complexA1B1C1D1-A2B2C2D2 in Figure 1(a), and 0-simplex are these vertices A1, B1, C1, D1, A2, B2, C2, D2, 1-simplex are these segments A1B1, C1D1, A2B2, C2D2, …, 2-simplex are these surfaces A1B1C1,A2B2C2,…, 3-simplex are these bodies B2-A1B1C1, A1-A2B2D2 and so on. There is a discrete gradient vector path A2→A2A1→ A1→A1B1→ B1→B1B2→ B2→B2C2→ C2→C2C1 →C1 on the 3-complex, composed by S0={A2,A1,B1,B2,C2,C1} and S1={A2A1,A1B1,B1B2,B2C2,C2C1}, so there are 0-chain A2+A1+B1+ B2+C2+C1 whose units come from S0 and 1-chain A2A1+A1B1+B1B2+B2C2+C2C1 whose units belong to S1. And then membranes from 0-chain or from 1-chain can compose a P system with chain structure. A2+A1+B1+B2+C2+C1 is an example of positive standard P chain system. 5A2A1+(-A1B1)+B1B2+(-3B2C2)+C2C1 can be called multiply generalized P chain system shown in Figure 1(b), where two-way arrow represents the repeated appearance of membrane, figure denotes the number of repeated appearance of its front membrane, that is to say, a1 appears 5 times and a3 3 times, usually 1 is omitted.The structure of P chain system.
(a)
ComplexA1B1C1D1-D2A2B2C2
(b)
P chain system based on discrete gradient vector path A2A1→A1B1→B1B2→B2C2→C2C1Property 1 (oriented property of P chain system).
There are three orientations of P chain system due to the orientation of simplex. What we entitle as P chain system with the same direction is that all the membranes are the same orientation, specifically in order to determine the direction of the P chain system, we need to predefine the orientation of complex, that is to say, if we stipulate the positive surfaceSq as positive, all the membranes from positive simplex of {Sq} form P chain system with positive orientation, marked by “+”, its membrane called positive membrane. On the contrary, all the membranes from the negative simplex of {-Sq} constitute the P chain system with negative orientation, marked by “−”, corresponding membrane called negative membrane. Moreover, if there are membranes from positive simplex or negative simplex at the same time in a P chain system, it is called P chain system with multiply orientation, marked by “×,” that is to say, in the P chain system with multiply orientation there are both positive membranes and negative membranes.Take the P chain systemA2A1→A1B1→B1B2→B2C2→C2C1 in Figure 1 for example. If we define clocklike orientation as the positive direction, P chain system A2A1→A1B1→B1B2→B2C2→C2C1 is positive one, and P chain system A1A2→B1A1→B2B1→C2B2→C1C2 is with negative orientation, while P chain system A2A1→B1A1→B1B2→B2C2→C1C2 is the example of multiply orientation.Property 2 (additive property of P chain system).
Supposing thatxq=g1s1q+g2s2q+⋯+gaqsaqq and yq=h1s1q+h2s2q+⋯+haqsaqq are any two q-chain, their addition xq+yq=(g1+h1)s1q+(g2+h2)s2q +⋯+(gaq+haq)saqq is also a q-chain. For the addition, all the q-chain of complex K are a free Abelian group, which is called q-chain group of K.Property 3 (precursory and subsequent relationships between adjacent membranes in P chain system).
Because P chain system is based on a discrete gradient vector path, the order of membranes is determined; that is, for a given P system with chain structure, the relationship between adjacent membranes is precursor or subsequent. For a P chain systemxp=r1α1p+r2α2p+⋯+rnαnp, where ri is integer and i=1,…,n, except the first membrane, usually the input membrane, for each membrane αip where i=2,…,n, its ahead membrane αi-1p is called its precursor; the relationship between αi-1p and αip is entitled as precursory relationship. Moreover, except for the last membrane, usually the output membrane, for arbitrary membrane αip, where i=1,…,(n-1), its back membrane αi+1p is called its subsequence; the relationship between αip and αi+1p is entitled as subsequent relationship.The algorithm for constructing the P system with chain structure is shown in Algorithm1.Algorithm 1:Construction algorithm of P system with chain structure.
INPUT: discrete Morse function M, the number of the membranes in P chain system N
OUTPUT: P system with chain structure
(1) Find out a discrete gradient vector path from the given discrete Morse functionM by the algorithm proposed in
literature [10];
(2) Find out setss_q consisted by all the q-simplex and s_q-1 consisted by all the (q-1)-simplex from the discrete gradient vector
path, noting that s_q and s_q-1 are ordered sets, ordered by the sequence of simplexes located in the discrete gradient
vector path;
(3) According to the number of membranesN in the P chain system, choosing adjacent N simplexes from s_q or s_q-1 as
membranes in the P chain system, constituting q-dimension or (q-1)-dimension P system with chain structure.


### 2.2.2. Description of Structure, Object, and Rule of P Chain System

For the structure of P chain system, we know that it is nonhierarchical, specifically if it is a chain structure based on discrete gradient vector path, while for the object, it is similar with the former P system, which is denoted by multisets, meaning thatw=a1M(a1)a2M(a2)⋯anM(an) is used to represent objects of each membrane. But considering the oriented property of P chain system, the membrane is divided into positive and negative one, so objects in membrane with different orientations are different too; for example, supporting that object in positive membrane is marked as a, then object in negative membrane is marked as a′ correspondingly. a and a′ are antimatter, meaning that they cannot coexist; when they encounter each other, they will counteract immediately. This is similar with positive and negative spikes in spiking neural P system, where rule αα′→λ makes their coexistence impossible.Based on the rules of former P system, combining the particularities of P system with chain structure, there are three main rules of P chain system: rewriting rules, communication rules, and forgetting rules.Rewriting rule is with the form ofu→v, where u and v, from the alphabet O, are the objects which represent the multisets, and this rule can be used in membrane a when and only when the object set w in a satisfies w⊇u. Rewriting rules are used to control the type and number of objects in membrane. Here are some target indications used to manage the movement of objects. They include tar1={here,out,in}, where “here” indicates that object remains in the membrane, “out” denotes that object leaves the membrane into its subsequence, and “in” shows that object is sent out to its precursor. So rewriting rule with target indication is formed as u→v, where u is a string representing multisets of objects from a given set O, and v is a string over O*  {here,out,in}. Usually they are formed as (a,tar), where a is the object from O and tar is here (usually omitted) or in or out. For example, P chain system xp=r1α1p+r2α2p+r3α3p+r4α4p; there are object a3b2c4 and rule a2bc3→a2bc(da,out)(ca,in) in membrane a2; the result of the execution of the rule is to produce 4a,1b,2c,1d, where 1d and 1a will be sent into subsequence a3 and 1c and 1a will be sent into precursor a1, eventually remaining a3b2c2 in membrane a2.Communication rules are used to manage the communication across the membranes, including symport rules and antiport rules. Here another target indicationtar2={pre,sub} is introduced, where “pre” indicates that which move to the precursor of the membrane and “sub” denotes that which move to its subsequence. So in communication rules, target indication is shown in pair, formed as (tar1,tar2), where tar1={here,out,in} and tar2={pre,sub} and where tar2 can be omitted, meaning that objects will be sent into the precursor or subsequence randomly. In a P chain system where the structure is determined, defining that the membrane where rule resides is αip, its precursor is αi-1p, and its subsequence is αi+1p. Symport rules, formed as (u,in) or (u,(in,pre)) or (u,(in,sub)), express that object u from membrane αi-1p or membrane αi+1p is sent into membrane αip, “pre” or “sub” specifying the source of object u. Also there is the form of (u,out) or (u,(out,pre)) or (u,(out,sub)), which means that object u from membrane αip is sent out into membrane αi-1p or membrane αi+1p randomly or determined by the target “pre” or “sub”. Antiport rules is formed as (u,out;v,in) or (u,(out,tar2);v,(in,tar2)), where (u,out;v,in) means that object u from membrane αip is sent out into membrane αi-1p or membrane αi+1p randomly, at the same time, object v from the membrane αi-1p or membrane αi+1p is sent into membrane αip, while rule (u,(out,tar2);v,(in,tar2)) elaborates the specific precursor and subsequence. In fact, the target indication (tar1,tar2) can be simplified as tar1tar2, for example, symport rule (u,(out,sub)) in membrane αip can be expressed as (u,outαi+1p), in the same way, antiport rule (u,(out,tar2);v,(in,tar2)) can be shown as (u,outαi+1p;v,inαi-1p), which means that object v from precursory membrane αi-1p is sent into membrane αip, at the same time object u from membrane αip is sent out into subsequent membrane αi+1p.Forgetting rule is defined as the form ofu→λ, where u is object over alphabet O which is used to represent multisets, and λ is null. The function of forgetting rule is to disappear some certain objects in membrane. A typical example of forgetting rule is objects a,a′ which are antimatter in membranes with different orientation, when they encounter with each other, they will counteract immediately, resulting from the execution of rule aa′→λ. In most situations, forgetting rule aa′→λ does not appear explicitly, but is defaulted to execute with the highest priority. Note that when execute this rule, if there are object a or a′ in membrane where the rule resides, its objects a or a′ will be used at first, if there is no object a or a′, supporting that there are enough object a or a′ in environment can be used to counteract the antimatter.


## 2.2.1. Definitions and Properties of P Chain System

Definition 5 (P system with chain structure).
Generalized P system with chain structure is written asXp=g1s1p+g2s2p+⋯+gapsapp, where gi is integer and |gi| represents the number of the membranes. Additionally, if ∀gi>0, XP represents positive generalized P system with chain structure, especially if ∀gi=1, XP denotes positive standard P chain system. Moreover, if ∀gi<0, XP represents negative generalized P chain system, particularly if ∀gi=-1, xp denotes negative standard P chain system. Furthermore, if ∃gi>0 or ∃gi<0, XP represents multiply generalized P chain system, especially if ∃gi=1 or ∃gi=-1, XP denotes multiply standard P chain system.Generally, what we call P system with chain structure is referred to the standard P chain system. Here is an example for the above definition. There is a complexA1B1C1D1-A2B2C2D2 in Figure 1(a), and 0-simplex are these vertices A1, B1, C1, D1, A2, B2, C2, D2, 1-simplex are these segments A1B1, C1D1, A2B2, C2D2, …, 2-simplex are these surfaces A1B1C1,A2B2C2,…, 3-simplex are these bodies B2-A1B1C1, A1-A2B2D2 and so on. There is a discrete gradient vector path A2→A2A1→ A1→A1B1→ B1→B1B2→ B2→B2C2→ C2→C2C1 →C1 on the 3-complex, composed by S0={A2,A1,B1,B2,C2,C1} and S1={A2A1,A1B1,B1B2,B2C2,C2C1}, so there are 0-chain A2+A1+B1+ B2+C2+C1 whose units come from S0 and 1-chain A2A1+A1B1+B1B2+B2C2+C2C1 whose units belong to S1. And then membranes from 0-chain or from 1-chain can compose a P system with chain structure. A2+A1+B1+B2+C2+C1 is an example of positive standard P chain system. 5A2A1+(-A1B1)+B1B2+(-3B2C2)+C2C1 can be called multiply generalized P chain system shown in Figure 1(b), where two-way arrow represents the repeated appearance of membrane, figure denotes the number of repeated appearance of its front membrane, that is to say, a1 appears 5 times and a3 3 times, usually 1 is omitted.The structure of P chain system.
(a)
ComplexA1B1C1D1-D2A2B2C2
(b)
P chain system based on discrete gradient vector path A2A1→A1B1→B1B2→B2C2→C2C1Property 1 (oriented property of P chain system).
There are three orientations of P chain system due to the orientation of simplex. What we entitle as P chain system with the same direction is that all the membranes are the same orientation, specifically in order to determine the direction of the P chain system, we need to predefine the orientation of complex, that is to say, if we stipulate the positive surfaceSq as positive, all the membranes from positive simplex of {Sq} form P chain system with positive orientation, marked by “+”, its membrane called positive membrane. On the contrary, all the membranes from the negative simplex of {-Sq} constitute the P chain system with negative orientation, marked by “−”, corresponding membrane called negative membrane. Moreover, if there are membranes from positive simplex or negative simplex at the same time in a P chain system, it is called P chain system with multiply orientation, marked by “×,” that is to say, in the P chain system with multiply orientation there are both positive membranes and negative membranes.Take the P chain systemA2A1→A1B1→B1B2→B2C2→C2C1 in Figure 1 for example. If we define clocklike orientation as the positive direction, P chain system A2A1→A1B1→B1B2→B2C2→C2C1 is positive one, and P chain system A1A2→B1A1→B2B1→C2B2→C1C2 is with negative orientation, while P chain system A2A1→B1A1→B1B2→B2C2→C1C2 is the example of multiply orientation.Property 2 (additive property of P chain system).
Supposing thatxq=g1s1q+g2s2q+⋯+gaqsaqq and yq=h1s1q+h2s2q+⋯+haqsaqq are any two q-chain, their addition xq+yq=(g1+h1)s1q+(g2+h2)s2q +⋯+(gaq+haq)saqq is also a q-chain. For the addition, all the q-chain of complex K are a free Abelian group, which is called q-chain group of K.Property 3 (precursory and subsequent relationships between adjacent membranes in P chain system).
Because P chain system is based on a discrete gradient vector path, the order of membranes is determined; that is, for a given P system with chain structure, the relationship between adjacent membranes is precursor or subsequent. For a P chain systemxp=r1α1p+r2α2p+⋯+rnαnp, where ri is integer and i=1,…,n, except the first membrane, usually the input membrane, for each membrane αip where i=2,…,n, its ahead membrane αi-1p is called its precursor; the relationship between αi-1p and αip is entitled as precursory relationship. Moreover, except for the last membrane, usually the output membrane, for arbitrary membrane αip, where i=1,…,(n-1), its back membrane αi+1p is called its subsequence; the relationship between αip and αi+1p is entitled as subsequent relationship.The algorithm for constructing the P system with chain structure is shown in Algorithm1.Algorithm 1:Construction algorithm of P system with chain structure.
INPUT: discrete Morse function M, the number of the membranes in P chain system N
OUTPUT: P system with chain structure
(1) Find out a discrete gradient vector path from the given discrete Morse functionM by the algorithm proposed in
literature [10];
(2) Find out setss_q consisted by all the q-simplex and s_q-1 consisted by all the (q-1)-simplex from the discrete gradient vector
path, noting that s_q and s_q-1 are ordered sets, ordered by the sequence of simplexes located in the discrete gradient
vector path;
(3) According to the number of membranesN in the P chain system, choosing adjacent N simplexes from s_q or s_q-1 as
membranes in the P chain system, constituting q-dimension or (q-1)-dimension P system with chain structure.


## 2.2.2. Description of Structure, Object, and Rule of P Chain System

For the structure of P chain system, we know that it is nonhierarchical, specifically if it is a chain structure based on discrete gradient vector path, while for the object, it is similar with the former P system, which is denoted by multisets, meaning thatw=a1M(a1)a2M(a2)⋯anM(an) is used to represent objects of each membrane. But considering the oriented property of P chain system, the membrane is divided into positive and negative one, so objects in membrane with different orientations are different too; for example, supporting that object in positive membrane is marked as a, then object in negative membrane is marked as a′ correspondingly. a and a′ are antimatter, meaning that they cannot coexist; when they encounter each other, they will counteract immediately. This is similar with positive and negative spikes in spiking neural P system, where rule αα′→λ makes their coexistence impossible.Based on the rules of former P system, combining the particularities of P system with chain structure, there are three main rules of P chain system: rewriting rules, communication rules, and forgetting rules.Rewriting rule is with the form ofu→v, where u and v, from the alphabet O, are the objects which represent the multisets, and this rule can be used in membrane a when and only when the object set w in a satisfies w⊇u. Rewriting rules are used to control the type and number of objects in membrane. Here are some target indications used to manage the movement of objects. They include tar1={here,out,in}, where “here” indicates that object remains in the membrane, “out” denotes that object leaves the membrane into its subsequence, and “in” shows that object is sent out to its precursor. So rewriting rule with target indication is formed as u→v, where u is a string representing multisets of objects from a given set O, and v is a string over O*  {here,out,in}. Usually they are formed as (a,tar), where a is the object from O and tar is here (usually omitted) or in or out. For example, P chain system xp=r1α1p+r2α2p+r3α3p+r4α4p; there are object a3b2c4 and rule a2bc3→a2bc(da,out)(ca,in) in membrane a2; the result of the execution of the rule is to produce 4a,1b,2c,1d, where 1d and 1a will be sent into subsequence a3 and 1c and 1a will be sent into precursor a1, eventually remaining a3b2c2 in membrane a2.Communication rules are used to manage the communication across the membranes, including symport rules and antiport rules. Here another target indicationtar2={pre,sub} is introduced, where “pre” indicates that which move to the precursor of the membrane and “sub” denotes that which move to its subsequence. So in communication rules, target indication is shown in pair, formed as (tar1,tar2), where tar1={here,out,in} and tar2={pre,sub} and where tar2 can be omitted, meaning that objects will be sent into the precursor or subsequence randomly. In a P chain system where the structure is determined, defining that the membrane where rule resides is αip, its precursor is αi-1p, and its subsequence is αi+1p. Symport rules, formed as (u,in) or (u,(in,pre)) or (u,(in,sub)), express that object u from membrane αi-1p or membrane αi+1p is sent into membrane αip, “pre” or “sub” specifying the source of object u. Also there is the form of (u,out) or (u,(out,pre)) or (u,(out,sub)), which means that object u from membrane αip is sent out into membrane αi-1p or membrane αi+1p randomly or determined by the target “pre” or “sub”. Antiport rules is formed as (u,out;v,in) or (u,(out,tar2);v,(in,tar2)), where (u,out;v,in) means that object u from membrane αip is sent out into membrane αi-1p or membrane αi+1p randomly, at the same time, object v from the membrane αi-1p or membrane αi+1p is sent into membrane αip, while rule (u,(out,tar2);v,(in,tar2)) elaborates the specific precursor and subsequence. In fact, the target indication (tar1,tar2) can be simplified as tar1tar2, for example, symport rule (u,(out,sub)) in membrane αip can be expressed as (u,outαi+1p), in the same way, antiport rule (u,(out,tar2);v,(in,tar2)) can be shown as (u,outαi+1p;v,inαi-1p), which means that object v from precursory membrane αi-1p is sent into membrane αip, at the same time object u from membrane αip is sent out into subsequent membrane αi+1p.Forgetting rule is defined as the form ofu→λ, where u is object over alphabet O which is used to represent multisets, and λ is null. The function of forgetting rule is to disappear some certain objects in membrane. A typical example of forgetting rule is objects a,a′ which are antimatter in membranes with different orientation, when they encounter with each other, they will counteract immediately, resulting from the execution of rule aa′→λ. In most situations, forgetting rule aa′→λ does not appear explicitly, but is defaulted to execute with the highest priority. Note that when execute this rule, if there are object a or a′ in membrane where the rule resides, its objects a or a′ will be used at first, if there is no object a or a′, supporting that there are enough object a or a′ in environment can be used to counteract the antimatter.


## 2.3. Formalization Definition of P Chain System

The formalization definition of standard P system with chain structure is described as followed:(2)∏=O,T,C,u,σ0,σ1,…,σm,syn,in,out.(1)
Ois the alphabet, and the element from O is called object;(2)
T is output alphabet, and T∈O;(3)
C is catalyst (C∈O-T); the element of C is unchanged during the evolutionary process of system; that is to say, the char of C does not disappear and there is no new char generated, but its participation is necessary for some certain rules to execute;(4)
u is the set of membrane structures, each membrane and its enclosed area are expressed as label set H, H={1,2,…,m};(5)
σ1,…,σm denote that there are m membranes with chain structure σ1,…,σm, and membrane σi is represented as σi=(ni,Ri), 0≤i≤m, where
①
ni≥0 denotes the number of objects of membrane σi at the beginning of calculation;②
Ri shows the limited set of rules in membrane σi, there are three main forms.
(i)
Rewriting rules are showed asu→v, where u from the alphabet O represents the multisets; v is the string over set O*{here,out,in}, written as (a,tar), where a is the object from O and tar is here (usually omitted), out or in.(ii)
Communication Rules include symport rules and antiport rules. Symport rules are formed as(u,(tar1,tar2)), and antiport rules are showed as (u,(tar1,tar2);v,(tar1,tar2)), where u,v are the objects of alphabet O representing the multisets, and tar1={here,out,in}, tar2={pre,sub}, tar1 is used to control the direction of object in or out of the membrane, and tar2 explains the object will be sent into which membrane.(iii)
Forgetting Rules are formed asu→λ, where u is the object over O representing the multisets, and λ represents null. The execution of forgetting rules makes the number of objects in membrane less.(6)
syn={1,2,…,m} is used to show the relationship among membranes in P chain system, for each 1≤i≤m, there is σ1→σ2→⋯→σm;(7)
in,out∈{1,2,…,m} denote the input and output membranes.


## 3. P Chain System for Arithmetic Operation

The calculating power of P system has been concerned and researched generally, and previous study has proved that NP-hard problem can be resolved by P system in polynomial time [5]. So there are crucial theoretical value and heightened practical significance if we can take advantage of the maximum parallelism of P system to improve computational efficiency for a series of calculation problems, such as arithmetic operation. The fundamental arithmetic operation includes addition, subtraction, multiplication, and division, which is the base of other complex operations. We try to achieve arithmetic operation with P chain system in order to explore more complex operation fulfilled by P chain system. Literature [11] has proved the possibility to fulfill arithmetic operation by P system. Based on this, P chain system for arithmetic operation is proposed here; compared with the former method, there are some improvements of both time performance and space performance.When designing the P chain system for arithmetic, standard P system with chain structure is chosen; that is to say, each membrane in P chain system appears only once. Moreover, we suppose that there are enough objects in environment which can be used for the execution of certain rules. Note that the P chain system for arithmetic operation designed now can only achieve the arithmetic operation between any two natural numbers, and the result of the calculation is shown as the number of object in output membrane.


### 3.1. P Chain System for Addition

In order to fulfill addition by P chain system, we select P system with single direction; that is to say, there is only membrane with positive orientation or negative orientation. Here is the example of P chain system with positive orientation to carry out the addition operation of P chain system. P system with chain structure for addition is designed as Figure2, and its formalization expression is described as follows:
(3)∏+Addition=O,σ1,σ2,in,out.
+: show that it is a P chain system with positive orientation; O={a,b}; σ1={n1,R1}, σ2={n2,R2}; n1={m∣a}, n2={n∣b}; R1={a→(b,out2)}, R2={b→(a,outo)}; in=1, out=o, here output membrane does not appear in Figure 2 and is represented by alphabet o.Figure 2
P chain system for addition.As shown in Figure2, there are two membranes with positive orientation, where m and n represent two natural numbers to add, and a and b are the objects of the P chain system, using the number change of object a and b to achieve the addition between any two natural numbers, here the number of object a are used to represent the calculating result. The specific process of P system with chain structure to fulfill addition is stated as followed. First, due to that there are operable rules in both membrane σ1 and σ2, in membrane σ1, rule R1 is executed and there will generate an object b sent into membrane σ2, at the same time, rule R2 in membrane σ2 is performed too and produces an object a sent into output membrane. Reactions in membrane σ1 and σ2 are done at the same time in the mode of maximum parallelism, and it will continue until all the object a in membrane σ1 are transformed into b and sent into membrane σ2. Then membrane σ1 will go into stable condition, and in membrane σ2 the rules will be used until all object b from membrane σ1 or σ2 are converted into a and sent into output membrane. Now membrane σ2 reaches stable, meaning that the whole P system is stable and the calculation ends, left m+n object a in output membrane. Until then, the P chain system completes the addition m+n of arbitrary two natural numbers m and n.


### 3.2. P Chain System for Subtraction

In order to achieve subtraction by P chain system, we select P chain system with multiplied orientation; that is, there are both membrane with positive orientation and negative orientation. P chain system for subtraction is designed as Figure3 and its formalization expression is described as followed.
(4)∏×Subtraction=O,σ1,σ2,in,out×: show that it is a P chain system with multiply orientation; O={a,a′,b}; σ1={n1,R1}, σ2={n2,R2}; n1={m∣a}, n2={n∣a′}; R1={{r11:am/am-1→(am-1,out2),m≠1}; {r12=a/a→(ab,out2)}}; R2={b/a′→(a′,out0)}; in=1, out=o, here output membrane isn’t shown in Figure 3 and is represented by alphabet o.Figure 3
P chain system for subtraction.As Figure3 showed, there is one membrane with positive orientation and the other is with negative orientation, where m and n represent any two natural numbers to subtract, specifically m is subtrahend and n is minuend, and b, a and a′ which are antimatter are the objects in the P chain system, using the number variation of object a and a′ to achieve the subtraction between any two natural numbers, here the number of object a′ are used to represent the calculating result. The process of P system with chain structure to achieve subtraction is described as followed. At first, rule in membrane σ1 with positive orientation will be used, where “/” denotes the condition for the rule to be executed, that is, only when the condition is met, the rule can be used. So rule r11 will be performed, producing m-1 object a sent into membrane σ2 with negative orientation, and when a and a′ encounter, they will disappear immediately by the defaulted rule aa′→λ. And then there is only one object a left in membrane σ1, which satisfies the executive condition of rule r12, and objects a and b generated will be sent into membrane σ2. The appearance of object b activates the rule R2, and n-m object a′ left in membrane σ2 will be sent into output membrane. Until then, the P chain system completes the subtraction n-m of any two natural numbers m and n.


### 3.3. P Chain System for Multiplication

In order to complete multiplication by P chain system, we select P chain system with single orientation, membrane with positive orientation or negative orientation. Here take the P chain system with positive orientation for example, and P chain system for multiplication is designed as Figure4 and its formalization expression is described as followed.
(5)∏+Multiplication=O,σ1,σ2,in,out
+: show that it is a P chain system with positive orientation; O={a,b}; σ1={n1,R1}, σ2={n2,R2}; n1={m∣a}, n2={0∣ϕ}; R1={a→(a,out2)}; R2={r21:a→bn;r22:bn→(bn,out0)}; in=1, out=o, here output membrane does not appear in Figure 4 and is represented by alphabet o.Figure 4
P chain system for multiplication.As shown in Figure4, there are two membranes with positive orientation, where m and n represent any two natural numbers to multiply, and a and b are the objects of the P chain system, using the number change of a and b to achieve the multiplication between any two natural numbers, here the number of object b are used to represent the calculating result. The process of P system with chain structure to fulfill multiplication is explained as followed. First, the existence of object a needed by rule R1 makes it usable in membrane σ1, due to the execution of rule a→(a,out2), the object a produced will be sent into membrane σ2, which will trigger rule r21 in membrane σ2. Here rule R2 is a chained rule, which contains two rule vectors. Referred to the literature [12], chained rule R is a vector set of rules, in the membrane if the first rule in the vector of chained rules R is applied, in the next step the rest of the rules from R will be applied in order in consecutive steps. And if any one rule from a vector of chained rules R which has already started to carry out cannot be used, the execution of R is dropped, that is, for the current application of R, the remaining rules are not executed anymore. So by rule r21, generate n object b, and then the executive condition of rule r22 is satisfied. So in membrane σ2 rule r22 will be used continuously until m object a in membrane σ1 are used up, and the whole system reaches stable, calculation ending and m*n object b left in output membrane. Until then, the P chain system completes the multiplication m*n of arbitrary two natural numbers m and n. Specific implementation is shown in Table 1.Table 1
The implementation of P chain system for multiplication.
Step
Membraneσ1
Membraneσ2
Output
Start
End
Start
End
1
a
m
a
→
(
a
,
ou
t
2
)
a
m
-
1
a
(
σ
1
)
a
(
σ
1
)
2
a
m
-
1
a
→
(
a
,
ou
t
2
)
a
m
-
2
a
(
σ
1
)
a
→
b
n
b
n
3
a
m
-
2
a
→
(
a
,
ou
t
2
)
a
m
-
3
a
(
σ
1
) bn
a
→
b
n bn→(bn,out)
b
n
b
n
⋮
m
a
a
→
(
a
,
ou
t
2
)
ϕ
a
(
σ
1
) bn
a
→
b
n bn→(bn,out)
b
n
b
(
m
-
2
)
n
m
+
1
a
(
σ
1
) bn
a
→
b
n bn→(bn,out)
b
n
b
(
m
-
1
)
n
m
+
2
a
(
σ
1
) bn
a
→
b
n bn→(bn,out)
b
n
b
m
n


### 3.4. P Chain System for Division

In order to achieve division by P chain system, we use P chain system with single orientation. Here taking the P chain system with positive orientation for example, P chain system for division is designed as Figure5 and its formalization definition is described as followed.
(6)∏+Division=O,σ1,σ2,in,out
+: show that it is a P chain system with positive orientation; O={a,b}; σ1={n1,R1}, σ2={n2,R2}; n1={m∣a}, n2={0∣ϕ}; R1={an→(an,out2)}, R2={r21:an→b;r22:b→(b,outo)}; in=1, out=o, here output membrane does not appear in Figure 5 and is represented by alphabet o.Figure 5
P chain system for division.As shown in Figure5, there are two membranes with positive orientation, where m and n represent any two natural numbers to divide, and a and b are the objects of the P chain system, using the number variation of object a and b to achieve the division between any two natural numbers, here the number of object b are used to represent the calculating result. Because at present the object defined in P chain system can only represent nonnegative integer, division taken into consideration here ignores the remainder. The process of P system with chain structure to fulfill division m/n is explained as followed. First, there are operable objects for rule R1 in membrane σ1, so the rule an→(an,out2) is used, generation n object a sent into membrane σ2, which activates the rule r21. Here rule R2 is a chained rule too. So by rule r21 produce one object b, and then the executive condition of rule r22 is met. So in membrane σ2 rule r22 will be performed continuously until the object a is used up or less than n and rule R1 isn’t executed any more, the whole system reaches stable, calculation ending and result is the number of object b left in output membrane. Until then, the P chain system completes the division m/n of arbitrary two natural numbers m and n. Specific implementation of exact division is shown in Table 2, and Table 3 gives the computational process of an example of nonexact division 9/2.Table 2
The implementation of P chain system for exact division.
Step
Membraneσ1
Membraneσ2
Output
Start
End
Start
End
1
a
m
-
(
t
-
3
)
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
n
a
n
(
σ
1
)
a
n
(
σ
1
)
2
a
m
-
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
2
n
a
n
(
σ
1
)
a
n
→
b
b
3
a
m
-
2
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
3
n
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
4
a
m
-
3
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
4
n
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
2
⋮
t
-
2 (t=m/n)
a
m
-
(
t
-
3
)
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
(
t
-
2
)
n
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
(
t
-
4
)
t
-
1 (t=m/n)
a
m
-
(
t
-
2
)
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
(
t
-
1
)
n
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
(
t
-
3
)
t (t=m/n)
a
m
-
(
t
-
1
)
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
t
n
=
ϕ
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
(
t
-
2
)
t
+
1 (t=m/n)
ϕ
ϕ
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
(
t
-
1
)
t
+
2 (t=m/n)
ϕ
ϕ
b
b
→
(
b
,
ou
t
0
)
b
b
tTable 3
The implementation of P chain system for nonexact division 9/2.
Step
Membraneσ1
Membraneσ2
output
Start
End
Start
End
1
a
9
a
n
→
(
a
n
,
ou
t
2
)
a
7
a
2
(
σ
1
)
a
2
(
σ
1
)
2
a
7
a
n
→
(
a
n
,
ou
t
2
)
a
5
a
2
(
σ
1
)
a
2
→
b
b
3
a
5
a
n
→
(
a
n
,
ou
t
2
)
a
3
a
2
(
σ
1
) b
a
2
→
b b→(b,out0)
b
b
4
a
3
a
n
→
(
a
n
,
ou
t
2
)
a
1
a
2
(
σ
1
) b
a
2
→
b b→(b,out0)
b
b
2
5
a
1
a
1
a
2
(
σ
1
) b
a
2
→
b b→(b,out0)
b
b
3
6
a
1
a
1
b
b
→
(
b
,
ou
t
0
)
b
b
4


### 3.5. The Analysis of System Performance

Time complexity used in literature [11] is referred to the number of execution of all rules. Following this way, the comparison of time complexity of the two different methods is shown in Table 4. We can see that the time complexity of arithmetic operation fulfilled by P system with chain structure has been improved obviously, especially the division, which can testify the efficiency and improvement of the new method. Meanwhile, the design of membrane structure and rule is simpler, more effective and more conducive to simulate than the former P system.Table 4
Comparison of time complexity of two methods.
Time complexity
Addition
Subtraction
Multiplication
Division
Literature [11]
O
(
n
+
m
+
1
)
O
(
n
+
m
+
1
)
O
(
m
)
O
(
n
+
m
+
q
+
1
+
1
)
This paper
O
(
max
⁡
{
m
,
n
}
)
O
(
n
)
O
(
m
+
2
)
O
(
m
/
n
+
2
)


## 3.1. P Chain System for Addition

In order to fulfill addition by P chain system, we select P system with single direction; that is to say, there is only membrane with positive orientation or negative orientation. Here is the example of P chain system with positive orientation to carry out the addition operation of P chain system. P system with chain structure for addition is designed as Figure2, and its formalization expression is described as follows:
(3)∏+Addition=O,σ1,σ2,in,out.
+: show that it is a P chain system with positive orientation; O={a,b}; σ1={n1,R1}, σ2={n2,R2}; n1={m∣a}, n2={n∣b}; R1={a→(b,out2)}, R2={b→(a,outo)}; in=1, out=o, here output membrane does not appear in Figure 2 and is represented by alphabet o.Figure 2
P chain system for addition.As shown in Figure2, there are two membranes with positive orientation, where m and n represent two natural numbers to add, and a and b are the objects of the P chain system, using the number change of object a and b to achieve the addition between any two natural numbers, here the number of object a are used to represent the calculating result. The specific process of P system with chain structure to fulfill addition is stated as followed. First, due to that there are operable rules in both membrane σ1 and σ2, in membrane σ1, rule R1 is executed and there will generate an object b sent into membrane σ2, at the same time, rule R2 in membrane σ2 is performed too and produces an object a sent into output membrane. Reactions in membrane σ1 and σ2 are done at the same time in the mode of maximum parallelism, and it will continue until all the object a in membrane σ1 are transformed into b and sent into membrane σ2. Then membrane σ1 will go into stable condition, and in membrane σ2 the rules will be used until all object b from membrane σ1 or σ2 are converted into a and sent into output membrane. Now membrane σ2 reaches stable, meaning that the whole P system is stable and the calculation ends, left m+n object a in output membrane. Until then, the P chain system completes the addition m+n of arbitrary two natural numbers m and n.


## 3.2. P Chain System for Subtraction

In order to achieve subtraction by P chain system, we select P chain system with multiplied orientation; that is, there are both membrane with positive orientation and negative orientation. P chain system for subtraction is designed as Figure3 and its formalization expression is described as followed.
(4)∏×Subtraction=O,σ1,σ2,in,out×: show that it is a P chain system with multiply orientation; O={a,a′,b}; σ1={n1,R1}, σ2={n2,R2}; n1={m∣a}, n2={n∣a′}; R1={{r11:am/am-1→(am-1,out2),m≠1}; {r12=a/a→(ab,out2)}}; R2={b/a′→(a′,out0)}; in=1, out=o, here output membrane isn’t shown in Figure 3 and is represented by alphabet o.Figure 3
P chain system for subtraction.As Figure3 showed, there is one membrane with positive orientation and the other is with negative orientation, where m and n represent any two natural numbers to subtract, specifically m is subtrahend and n is minuend, and b, a and a′ which are antimatter are the objects in the P chain system, using the number variation of object a and a′ to achieve the subtraction between any two natural numbers, here the number of object a′ are used to represent the calculating result. The process of P system with chain structure to achieve subtraction is described as followed. At first, rule in membrane σ1 with positive orientation will be used, where “/” denotes the condition for the rule to be executed, that is, only when the condition is met, the rule can be used. So rule r11 will be performed, producing m-1 object a sent into membrane σ2 with negative orientation, and when a and a′ encounter, they will disappear immediately by the defaulted rule aa′→λ. And then there is only one object a left in membrane σ1, which satisfies the executive condition of rule r12, and objects a and b generated will be sent into membrane σ2. The appearance of object b activates the rule R2, and n-m object a′ left in membrane σ2 will be sent into output membrane. Until then, the P chain system completes the subtraction n-m of any two natural numbers m and n.


## 3.3. P Chain System for Multiplication

In order to complete multiplication by P chain system, we select P chain system with single orientation, membrane with positive orientation or negative orientation. Here take the P chain system with positive orientation for example, and P chain system for multiplication is designed as Figure4 and its formalization expression is described as followed.
(5)∏+Multiplication=O,σ1,σ2,in,out
+: show that it is a P chain system with positive orientation; O={a,b}; σ1={n1,R1}, σ2={n2,R2}; n1={m∣a}, n2={0∣ϕ}; R1={a→(a,out2)}; R2={r21:a→bn;r22:bn→(bn,out0)}; in=1, out=o, here output membrane does not appear in Figure 4 and is represented by alphabet o.Figure 4
P chain system for multiplication.As shown in Figure4, there are two membranes with positive orientation, where m and n represent any two natural numbers to multiply, and a and b are the objects of the P chain system, using the number change of a and b to achieve the multiplication between any two natural numbers, here the number of object b are used to represent the calculating result. The process of P system with chain structure to fulfill multiplication is explained as followed. First, the existence of object a needed by rule R1 makes it usable in membrane σ1, due to the execution of rule a→(a,out2), the object a produced will be sent into membrane σ2, which will trigger rule r21 in membrane σ2. Here rule R2 is a chained rule, which contains two rule vectors. Referred to the literature [12], chained rule R is a vector set of rules, in the membrane if the first rule in the vector of chained rules R is applied, in the next step the rest of the rules from R will be applied in order in consecutive steps. And if any one rule from a vector of chained rules R which has already started to carry out cannot be used, the execution of R is dropped, that is, for the current application of R, the remaining rules are not executed anymore. So by rule r21, generate n object b, and then the executive condition of rule r22 is satisfied. So in membrane σ2 rule r22 will be used continuously until m object a in membrane σ1 are used up, and the whole system reaches stable, calculation ending and m*n object b left in output membrane. Until then, the P chain system completes the multiplication m*n of arbitrary two natural numbers m and n. Specific implementation is shown in Table 1.Table 1
The implementation of P chain system for multiplication.
Step
Membraneσ1
Membraneσ2
Output
Start
End
Start
End
1
a
m
a
→
(
a
,
ou
t
2
)
a
m
-
1
a
(
σ
1
)
a
(
σ
1
)
2
a
m
-
1
a
→
(
a
,
ou
t
2
)
a
m
-
2
a
(
σ
1
)
a
→
b
n
b
n
3
a
m
-
2
a
→
(
a
,
ou
t
2
)
a
m
-
3
a
(
σ
1
) bn
a
→
b
n bn→(bn,out)
b
n
b
n
⋮
m
a
a
→
(
a
,
ou
t
2
)
ϕ
a
(
σ
1
) bn
a
→
b
n bn→(bn,out)
b
n
b
(
m
-
2
)
n
m
+
1
a
(
σ
1
) bn
a
→
b
n bn→(bn,out)
b
n
b
(
m
-
1
)
n
m
+
2
a
(
σ
1
) bn
a
→
b
n bn→(bn,out)
b
n
b
m
n


## 3.4. P Chain System for Division

In order to achieve division by P chain system, we use P chain system with single orientation. Here taking the P chain system with positive orientation for example, P chain system for division is designed as Figure5 and its formalization definition is described as followed.
(6)∏+Division=O,σ1,σ2,in,out
+: show that it is a P chain system with positive orientation; O={a,b}; σ1={n1,R1}, σ2={n2,R2}; n1={m∣a}, n2={0∣ϕ}; R1={an→(an,out2)}, R2={r21:an→b;r22:b→(b,outo)}; in=1, out=o, here output membrane does not appear in Figure 5 and is represented by alphabet o.Figure 5
P chain system for division.As shown in Figure5, there are two membranes with positive orientation, where m and n represent any two natural numbers to divide, and a and b are the objects of the P chain system, using the number variation of object a and b to achieve the division between any two natural numbers, here the number of object b are used to represent the calculating result. Because at present the object defined in P chain system can only represent nonnegative integer, division taken into consideration here ignores the remainder. The process of P system with chain structure to fulfill division m/n is explained as followed. First, there are operable objects for rule R1 in membrane σ1, so the rule an→(an,out2) is used, generation n object a sent into membrane σ2, which activates the rule r21. Here rule R2 is a chained rule too. So by rule r21 produce one object b, and then the executive condition of rule r22 is met. So in membrane σ2 rule r22 will be performed continuously until the object a is used up or less than n and rule R1 isn’t executed any more, the whole system reaches stable, calculation ending and result is the number of object b left in output membrane. Until then, the P chain system completes the division m/n of arbitrary two natural numbers m and n. Specific implementation of exact division is shown in Table 2, and Table 3 gives the computational process of an example of nonexact division 9/2.Table 2
The implementation of P chain system for exact division.
Step
Membraneσ1
Membraneσ2
Output
Start
End
Start
End
1
a
m
-
(
t
-
3
)
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
n
a
n
(
σ
1
)
a
n
(
σ
1
)
2
a
m
-
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
2
n
a
n
(
σ
1
)
a
n
→
b
b
3
a
m
-
2
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
3
n
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
4
a
m
-
3
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
4
n
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
2
⋮
t
-
2 (t=m/n)
a
m
-
(
t
-
3
)
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
(
t
-
2
)
n
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
(
t
-
4
)
t
-
1 (t=m/n)
a
m
-
(
t
-
2
)
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
(
t
-
1
)
n
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
(
t
-
3
)
t (t=m/n)
a
m
-
(
t
-
1
)
n
a
n
→
(
a
n
,
ou
t
2
)
a
m
-
t
n
=
ϕ
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
(
t
-
2
)
t
+
1 (t=m/n)
ϕ
ϕ
a
n
(
σ
1
) b
a
n
→
b b→(b,out0)
b
b
(
t
-
1
)
t
+
2 (t=m/n)
ϕ
ϕ
b
b
→
(
b
,
ou
t
0
)
b
b
tTable 3
The implementation of P chain system for nonexact division 9/2.
Step
Membraneσ1
Membraneσ2
output
Start
End
Start
End
1
a
9
a
n
→
(
a
n
,
ou
t
2
)
a
7
a
2
(
σ
1
)
a
2
(
σ
1
)
2
a
7
a
n
→
(
a
n
,
ou
t
2
)
a
5
a
2
(
σ
1
)
a
2
→
b
b
3
a
5
a
n
→
(
a
n
,
ou
t
2
)
a
3
a
2
(
σ
1
) b
a
2
→
b b→(b,out0)
b
b
4
a
3
a
n
→
(
a
n
,
ou
t
2
)
a
1
a
2
(
σ
1
) b
a
2
→
b b→(b,out0)
b
b
2
5
a
1
a
1
a
2
(
σ
1
) b
a
2
→
b b→(b,out0)
b
b
3
6
a
1
a
1
b
b
→
(
b
,
ou
t
0
)
b
b
4


## 3.5. The Analysis of System Performance

Time complexity used in literature [11] is referred to the number of execution of all rules. Following this way, the comparison of time complexity of the two different methods is shown in Table 4. We can see that the time complexity of arithmetic operation fulfilled by P system with chain structure has been improved obviously, especially the division, which can testify the efficiency and improvement of the new method. Meanwhile, the design of membrane structure and rule is simpler, more effective and more conducive to simulate than the former P system.Table 4
Comparison of time complexity of two methods.
Time complexity
Addition
Subtraction
Multiplication
Division
Literature [11]
O
(
n
+
m
+
1
)
O
(
n
+
m
+
1
)
O
(
m
)
O
(
n
+
m
+
q
+
1
+
1
)
This paper
O
(
max
⁡
{
m
,
n
}
)
O
(
n
)
O
(
m
+
2
)
O
(
m
/
n
+
2
)


## 4. Simulation of Arithmetic Operation P Chain System

The simulation of P system has a vital practical significance, and there has been a series of success P system simulation software which can be obtained from P system web page [13]. Based on this, in this paper we try to do the simulation program of P chain system for arithmetic operation, as a result, it has stood out its lower time-cost and higher efficiency significantly. The development platform of the system is Microsoft Visual Studio 2008 on Windows 7 and the development language is C#. The whole system can operate normally, and can produce the executable file, which is with portability and robustness.


### 4.1. Description of Storage Mode of the Simulation System

During the process to develop system, we need to choose the appropriate storage mode for different elements, and the specification is demonstrated as followed [14].We have known that we need to store the membrane structure, object and rule. Here we abstract those contents in each P system instance as an input file, marked “pcs” as the expanded name, for example, the input file of a P system to achieve the addition operation is named as “Addition.pcs”. And taking the addition operation for example, the input file which includes the definition of the membrane structure, object and rule is showed in Table5.Table 5
1
Start
leading flag
2
1
→
2
→
O
membrane
3
O
output membrane label
4
a b
multisets
5
a
output multisets
6
Initm1
initialization membrane1
7
InitM
initialization the multisets in membrane1
8
8 0
8a, 0 b in multisets
9
InitR
initialization the rule sets in membrane1
10
a
→
(
b
,
ou
t
2
)
the0th rule in membrane 1
11
PrioR
the priority of the rules in membrane1
12
—
the null priority set
13
Initm2
initialization membrane2
14
InitM
initialization the multisets in membrane2
15
0 6
0a, 6 b in multisets
16
InitR
initialization the rule sets in membrane 2
17
b
→
(
a
,
ou
t
0
)
the0th rule in membrane 2
18
PrioR
the priority of the rules in membrane2
19
—
the null priority set
20
InitmO
initialization output membraneO
21
InitM
initialization the multisets in membraneO
22
0 0
0a, 0 b in multisets
23
InitR
initialization the rule sets in membraneO
24
—
the null rule in membraneO
25
PrioR
the priority of the rules in membraneO
26
—
the null priority set
27
End
ending flagAfter explain the structure, object and rule in a P chain system which need stored, how to store them is the next consideration, which is also the problem that needs to be resolved in the process of system initialization.For the object multisets in the P chain system, it is stored by the form of nonnegative integer. The reason that we do not choose char is when the number of the object is large, the length of char may be very long, not only occupying large storage space, but also consuming much time when read. However, by using the INT array, huge amount of data can be denoted briefly.For the rules in the P chain system, they are input into the system in the form of strings. If we want to fulfill the correspondence between the rules and object multisets, some rule transformations are needed. The way is that, first, determine the alphabets used in the P chain system, taking the P chain system for addition operation for example, the alphabet set{a,b} and the rule a→(b,out2) involved in membrane 1, we need divide the rule into two parts, namely the former and the latter, and store them respectively. The former part of the rule is presented as [1,0], meaning that there are 1 object a and 0 object b, and the latter part of the rule is denoted as [0,0;1] and [0,1;2], noting that the number 1 and 2 after semicolon display the membrane 1, 2, and the part before semicolon shows the change of numbers of objects. For the rule a→(b,out2), we know that after the operation of the rule, there are 1 object a consumed and no consumption of object b in membrane 1, and in membrane 2, the number of object a are unchanged and the object b is added one more.For the storage of the structure of P chain system, due to the special chain structure, we choose linear structure to save. Specifically, it is a kind of linear list, that is to say, two elements which are adjacent logically are adjacent physically. Here we use the vector representation, and there are three marks in each storage unit, the node mark(I), precursor node mark (Pre) and subsequent node mark (Sub). Take the P chain system 1→2→3→4→5→O for example, its storage form showed as Table 6.Table 6
Storage of P chain system.
Storage position
0
1
2
3
4
5
Node mark (I)
1
2
3
4
5
O
Precursor node mark (pre)
#
1
2
3
4
5
Subsequent node mark (sub)
2
3
4
5
O
#Following is the code of object and rule for P chain system for addition operation to illustrate the specific storage mode.(1)
int⁡[]Ob21=newint⁡[]{num1};(2)
int⁡[]Ob22=newint⁡[]{num2};(3)
String[,]R21=newString[,]{{1,0},{0,0},{1}};(4)
String[,]R22=newString[,]{{0,0},{0,1},{2}}.Here line (1) and (2) are the storage way of objects, num1 and num2 are any two nature numbers to add; line (3)-(4) are the storage of rulea→(b,out2), using two-dimension string array, where the first dimension shows the rule is divided to three parts, and the second dimension displays the number of object a, object b and the label of membrane, for line (3) as an example, the last {1} means this is in the membrane 1, the {1,0} denotes before rule execution there are 1 object a and 0 object b, and {0,0} explains after rule execution there are 0 object a and b left the membrane 1.


### 4.2. Description of Rules Selection Algorithm

The strong computing power of membrane computing is largely due to its maximum parallelism, in the theoretical aspect, the rules in the membrane are allowed to perform freely until there are no rules can be selected. But in the specific process to fulfill the simulation of P system, we need to consider the order of the rule executed and the phenomenon “competition for resource” among the implement process of rules.For the order of the rules execution, there are many exploratory researches, for example, in the literature [12] chained-rule was proposed, which is a new way to design rules in the P system, where rules are arranged as a form of a chain, meaning they are used by a sequence in the chain. Supposing that there is a chained rule R, which contains several vectors of the rule r1,r2,…,rn, in the membrane if the first rule r1 of chained rule R is applied, then in the next step the rest of the rules from R will be applied in order in consecutive steps. Only when the condition of certain vector rule ri is not satisfied or there is no more vector rules can be used, the chained rule R will halt.In fact, all the ways to explore the order of rule execution are to solve the priority problem, here are two main rule priorities, the strong relationship and the weak one. The strong relationship is referred to that a rule can be used when and only when there is no prior rule can be used, while the weak relationship is defined as for a ruleR, if there are prior rules than it, meaning the condition to perform the prior is also met, no matter the prior rules are used or not, the rule R cannot be used. For example, for the objects abc and rules 1: ab→ac; 2: ab→bc; 3: a→b; 4: b→c with priority 2>3 and 2>4, referring to the definition of strong relationship, there are three possible rule choices {1,3}, {1,4} and {2}, but considering the weak relationship, there are only two choices {1} and {2}, and this is because the condition that is satisfied to rule 1 is also met to rule 2, even if rule 2 is not used, when rule 1 is executed, rule 3 and 4 cannot be used. In this paper, we choose the weak one as the standard in the simulation of P chain system. And also some tentative algorithms are given to solve the problem of “competition of resource”. The algorithm of rule selection for simulating P chain system is shown in Algorithm 2.Algorithm 2:Rule selection algorithm for simulation of P chain system.
INPUT: object multisets of membrane M, rule set R, priority set of rule execution P (P is represented by the ordered pairs
of rule labels, such as 1>2, denoted as 1,2; for the chained rules, P is showed as ic,i(c+1), i,c=1,2,…, meaning
to be performed by order);
OUTPUT: rule set chosen to be used A
(1) For every rule in the setR, if each value in the INT vector corresponded to the former of the rule is no more than
corresponding value inM, rule r is put into the candidate rule set L.
(2) For each ordered pairsp,q in priority set P, setting A=L, if rule rp and rq are both in L, then if p=ic, q=i(c+1),
thenrp, rq are left in A, and the sequence is rp, rq, otherwise delete the less prior rule rq.Now we have set the executive priority of rules, which has reduced the problem of “competition for resource” in some extend, but for the rules without priority, the problem is also existed, here we make full use of another significant characteristic of P system—“Randomness”, meaning that if there are two rules which compete for resource, randomly select one to use. The specific algorithm to handle “competition for resource” further is shown in Algorithm3.Algorithm 3:Rule selection algorithm with “competition for resource”.
INPUT: rule set A (the output of Algorithm 2)
OUTPUT: rule set Lp without competition for resource
(1) Select one ruler form A randomly, adding r into Lp, and delete r from A at the same time.
(2) For every ruler′ in A except r, if there is competition for resource between r′ and r,
deleter′ from A. If A is not null, return (1), else output Lp.


### 4.3. Demonstration of Simulation of P Chain System

The interface of simulation software of P chain system for implementing arithmetic operation is shown in Figure6(a). Here the first number and the second number represent the two positive integers used to operate, and there are four kinds of operators +,-,*,/ to be chosen. When you have chosen a kind of operator and clicked on the “calculate” button, the calculating result will be shown in the resulting box, and when you have selected to use clear button, the data will be eliminated from the textbox and the next calculation is ready. Figures 6(b), 6(c), 6(d), 6(e), and 6(f) show the realization to calculate 2+9, 17-9, 9*22, 98/14, 10/3 is possible.Simulation interface of P chain system for arithmetic operation.
(a)
Simulation interface
(b)
“+”
(c)
“−”
(d)
“*”
(e)
“/” (exact division)
(f)
“/” (aliquant division)


## 4.1. Description of Storage Mode of the Simulation System

During the process to develop system, we need to choose the appropriate storage mode for different elements, and the specification is demonstrated as followed [14].We have known that we need to store the membrane structure, object and rule. Here we abstract those contents in each P system instance as an input file, marked “pcs” as the expanded name, for example, the input file of a P system to achieve the addition operation is named as “Addition.pcs”. And taking the addition operation for example, the input file which includes the definition of the membrane structure, object and rule is showed in Table5.Table 5
1
Start
leading flag
2
1
→
2
→
O
membrane
3
O
output membrane label
4
a b
multisets
5
a
output multisets
6
Initm1
initialization membrane1
7
InitM
initialization the multisets in membrane1
8
8 0
8a, 0 b in multisets
9
InitR
initialization the rule sets in membrane1
10
a
→
(
b
,
ou
t
2
)
the0th rule in membrane 1
11
PrioR
the priority of the rules in membrane1
12
—
the null priority set
13
Initm2
initialization membrane2
14
InitM
initialization the multisets in membrane2
15
0 6
0a, 6 b in multisets
16
InitR
initialization the rule sets in membrane 2
17
b
→
(
a
,
ou
t
0
)
the0th rule in membrane 2
18
PrioR
the priority of the rules in membrane2
19
—
the null priority set
20
InitmO
initialization output membraneO
21
InitM
initialization the multisets in membraneO
22
0 0
0a, 0 b in multisets
23
InitR
initialization the rule sets in membraneO
24
—
the null rule in membraneO
25
PrioR
the priority of the rules in membraneO
26
—
the null priority set
27
End
ending flagAfter explain the structure, object and rule in a P chain system which need stored, how to store them is the next consideration, which is also the problem that needs to be resolved in the process of system initialization.For the object multisets in the P chain system, it is stored by the form of nonnegative integer. The reason that we do not choose char is when the number of the object is large, the length of char may be very long, not only occupying large storage space, but also consuming much time when read. However, by using the INT array, huge amount of data can be denoted briefly.For the rules in the P chain system, they are input into the system in the form of strings. If we want to fulfill the correspondence between the rules and object multisets, some rule transformations are needed. The way is that, first, determine the alphabets used in the P chain system, taking the P chain system for addition operation for example, the alphabet set{a,b} and the rule a→(b,out2) involved in membrane 1, we need divide the rule into two parts, namely the former and the latter, and store them respectively. The former part of the rule is presented as [1,0], meaning that there are 1 object a and 0 object b, and the latter part of the rule is denoted as [0,0;1] and [0,1;2], noting that the number 1 and 2 after semicolon display the membrane 1, 2, and the part before semicolon shows the change of numbers of objects. For the rule a→(b,out2), we know that after the operation of the rule, there are 1 object a consumed and no consumption of object b in membrane 1, and in membrane 2, the number of object a are unchanged and the object b is added one more.For the storage of the structure of P chain system, due to the special chain structure, we choose linear structure to save. Specifically, it is a kind of linear list, that is to say, two elements which are adjacent logically are adjacent physically. Here we use the vector representation, and there are three marks in each storage unit, the node mark(I), precursor node mark (Pre) and subsequent node mark (Sub). Take the P chain system 1→2→3→4→5→O for example, its storage form showed as Table 6.Table 6
Storage of P chain system.
Storage position
0
1
2
3
4
5
Node mark (I)
1
2
3
4
5
O
Precursor node mark (pre)
#
1
2
3
4
5
Subsequent node mark (sub)
2
3
4
5
O
#Following is the code of object and rule for P chain system for addition operation to illustrate the specific storage mode.(1)
int⁡[]Ob21=newint⁡[]{num1};(2)
int⁡[]Ob22=newint⁡[]{num2};(3)
String[,]R21=newString[,]{{1,0},{0,0},{1}};(4)
String[,]R22=newString[,]{{0,0},{0,1},{2}}.Here line (1) and (2) are the storage way of objects, num1 and num2 are any two nature numbers to add; line (3)-(4) are the storage of rulea→(b,out2), using two-dimension string array, where the first dimension shows the rule is divided to three parts, and the second dimension displays the number of object a, object b and the label of membrane, for line (3) as an example, the last {1} means this is in the membrane 1, the {1,0} denotes before rule execution there are 1 object a and 0 object b, and {0,0} explains after rule execution there are 0 object a and b left the membrane 1.


## 4.2. Description of Rules Selection Algorithm

The strong computing power of membrane computing is largely due to its maximum parallelism, in the theoretical aspect, the rules in the membrane are allowed to perform freely until there are no rules can be selected. But in the specific process to fulfill the simulation of P system, we need to consider the order of the rule executed and the phenomenon “competition for resource” among the implement process of rules.For the order of the rules execution, there are many exploratory researches, for example, in the literature [12] chained-rule was proposed, which is a new way to design rules in the P system, where rules are arranged as a form of a chain, meaning they are used by a sequence in the chain. Supposing that there is a chained rule R, which contains several vectors of the rule r1,r2,…,rn, in the membrane if the first rule r1 of chained rule R is applied, then in the next step the rest of the rules from R will be applied in order in consecutive steps. Only when the condition of certain vector rule ri is not satisfied or there is no more vector rules can be used, the chained rule R will halt.In fact, all the ways to explore the order of rule execution are to solve the priority problem, here are two main rule priorities, the strong relationship and the weak one. The strong relationship is referred to that a rule can be used when and only when there is no prior rule can be used, while the weak relationship is defined as for a ruleR, if there are prior rules than it, meaning the condition to perform the prior is also met, no matter the prior rules are used or not, the rule R cannot be used. For example, for the objects abc and rules 1: ab→ac; 2: ab→bc; 3: a→b; 4: b→c with priority 2>3 and 2>4, referring to the definition of strong relationship, there are three possible rule choices {1,3}, {1,4} and {2}, but considering the weak relationship, there are only two choices {1} and {2}, and this is because the condition that is satisfied to rule 1 is also met to rule 2, even if rule 2 is not used, when rule 1 is executed, rule 3 and 4 cannot be used. In this paper, we choose the weak one as the standard in the simulation of P chain system. And also some tentative algorithms are given to solve the problem of “competition of resource”. The algorithm of rule selection for simulating P chain system is shown in Algorithm 2.Algorithm 2:Rule selection algorithm for simulation of P chain system.
INPUT: object multisets of membrane M, rule set R, priority set of rule execution P (P is represented by the ordered pairs
of rule labels, such as 1>2, denoted as 1,2; for the chained rules, P is showed as ic,i(c+1), i,c=1,2,…, meaning
to be performed by order);
OUTPUT: rule set chosen to be used A
(1) For every rule in the setR, if each value in the INT vector corresponded to the former of the rule is no more than
corresponding value inM, rule r is put into the candidate rule set L.
(2) For each ordered pairsp,q in priority set P, setting A=L, if rule rp and rq are both in L, then if p=ic, q=i(c+1),
thenrp, rq are left in A, and the sequence is rp, rq, otherwise delete the less prior rule rq.Now we have set the executive priority of rules, which has reduced the problem of “competition for resource” in some extend, but for the rules without priority, the problem is also existed, here we make full use of another significant characteristic of P system—“Randomness”, meaning that if there are two rules which compete for resource, randomly select one to use. The specific algorithm to handle “competition for resource” further is shown in Algorithm3.Algorithm 3:Rule selection algorithm with “competition for resource”.
INPUT: rule set A (the output of Algorithm 2)
OUTPUT: rule set Lp without competition for resource
(1) Select one ruler form A randomly, adding r into Lp, and delete r from A at the same time.
(2) For every ruler′ in A except r, if there is competition for resource between r′ and r,
deleter′ from A. If A is not null, return (1), else output Lp.


## 4.3. Demonstration of Simulation of P Chain System

The interface of simulation software of P chain system for implementing arithmetic operation is shown in Figure6(a). Here the first number and the second number represent the two positive integers used to operate, and there are four kinds of operators +,-,*,/ to be chosen. When you have chosen a kind of operator and clicked on the “calculate” button, the calculating result will be shown in the resulting box, and when you have selected to use clear button, the data will be eliminated from the textbox and the next calculation is ready. Figures 6(b), 6(c), 6(d), 6(e), and 6(f) show the realization to calculate 2+9, 17-9, 9*22, 98/14, 10/3 is possible.Simulation interface of P chain system for arithmetic operation.
(a)
Simulation interface
(b)
“+”
(c)
“−”
(d)
“*”
(e)
“/” (exact division)
(f)
“/” (aliquant division)


## 5. Summary and Prospect

In this paper, a novel P system with chain structure is introduced, which combines membrane computing and discrete Morse theory and takes use of the advantages of discrete gradient vector path. As one of new P system, it has some theoretical and practical contributions.First, the definition of structure, object and rule of P system with chain structure is proposed, especially its differences with the former P system, mainly referred to its chain structure, such as its oriented property, additive property, and precursory and subsequent relationships. It contributes to enrich the theoretical framework of P system research. Second, the application on arithmetic operation by P chain system is demonstrated, and the specific model and rules of P chain system used are shown in detail. Compared with the former methods, the new thinking is more effective both in time and space complexity. Last, the simulation system of P chain system for arithmetic operation is given, and the feasibility of the system is proved, which demonstrates the computational feasibility and effectiveness of P system with chain structure. This is a good start to simulate P system, and is also an exploratory way to show and take full use of the advantages of P system to solve some practical problems.While we should admit that there are some insufficiencies in this paper; for example, the application on arithmetic operation is not connected with the rules proposed so closely and does not display the computing power of P chain system obviously, and the function of the simulation system is a little easy. All of these should be taken into consideration for further study. Based on the work in this paper, there are many other studies can be furthered on. For example, there are some special properties of P chain system, and how to use these particularities to enhance the computational power of P system is a question deserved to think. Also, whether there are some special applications which may be solved by P chain system more efficiently or not is a meaningful question too. Moreover, the simulation of P system with chain structure to fulfill more functions is a big challenge and needed to study more.



---

*Source: 123960-2015-01-21.xml*