# A Linear Time Complexity of Breadth-First Search UsingP System with Membrane Division

Authors: Einallah Salehi; Siti Mariyam Shamsuddin; Kourosh Nemati
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

One of the known methods for solving the problems with exponential time complexity such as NP-complete problems is using the brute force algorithms. Recently, a new parallel computational framework called Membrane Computing is introduced which can be applied in brute force algorithms. The usual way to find a solution for the problems with exponential time complexity with Membrane Computing techniques is byP System with active membrane using division rule. It makes an exponential workspace and solves the problems with exponential complexity in a polynomial (even linear) time. On the other hand, searching is currently one of the most used methods for finding solution for problems in real life, that the blind search algorithms are accurate, but their time complexity is exponential such as breadth-first search (BFS) algorithm. In this paper, we proposed a new approach for implementation of BFS by using P system with division rule technique for first time. The theorem shows time complexity of BSF in this framework on randomly binary trees reduced from O(2d) to O(d).


---

## Body

## 1. Introduction

Membrane Computing, introduced in 1998, is an area of study in computer science [1]. Membrane Computing could be considered as a framework in the distributed parallel computing, and it is inspired from the computing ideas, structures, models, the living cells activities, and the cells organized in a hierarchy. Using Membrane Computing, we obtain a computing device called P system. Several membranes are included in the basic model of a P system, embedded in a main membrane that is known as the skin. The Euclidean space is divided by membranes into some regions consisting of some objects (that are generally signified by alphabetical symbols) and the evolution rules. Applying these rules, the objects can be evolved and/or moved from a region to their adjacent regions. Typically, these rules are employed in a nondeterministic and maximally parallel manner. After an initial system configuration, the computation starts, and it terminates once no evolution rule could be applied. The computation result can be a multiset of objects that are embedded in an output membrane or discharged from the system skin.So far, several types ofP system have been introduced and investigated [1–3]. P system with active membrane is one of the most well-known P systems in which the number of membranes increases during a computation by using some division rules, creation rules, or separation rules [4–7] (we call them in short P system with membrane division or P system with division rule, P system with membrane creation or P system with creation rule, and P system with separation rule, respectively).  They make models of the division or creation of the cells in the nature. In the initial variant of P system with division rule [8], the division rules were defined in such a way that, from the division of a membrane, we could always obtain two membranes (we call it a 2-bounded division or, in short, division rule). A generalization was defined in [9] where a membrane can be divided into several (but a finite number of) membranes (we call it a k-bounded division). Also in P system with creation rules, some objects are so productive that they create membranes [10]. Thus, new membranes can be made ​​exponentially.Most ofP systems are proved to be universal [1, 11–14] and efficient [8, 15, 16]. Several studies have been performed on the P system with active membrane. In most of these studies, the time complexity is reduced from exponential to polynomial or linear time in an exponential workspace or, at least, they have improved the time complexity as follows: using P system with division rules; it was shown that the NP-complete problem SAT can be solved in a linear time [8]. As investigated in [9], the HPP can be solved using P systems with k-bounded division rules in polynomial time, but in [17], it was shown that HPP can be solved using P systems with division (2-bounded)  rules in  which the time complexity for this problem was linear, and the knapsack problem has been solved using a family of deterministic P system with division rules presented in [18] in linear time. Using P systems, some other problems (mostly NP-complete) have been solved in linear or polynomial time complexity, for example, SAT problem in [7, 19, 20], graph problem [21], subset sum [22], 3-COL problem [23], vertex cover problem [24], HAM-CYCLE problem [25], and HPP problem in [10]. P systems are also used to solve PSPACE problems [26–29].In all researches conducted on this area of study, the time units are considered as the steps of computation in aP system,  which are performed in parallel, in evolution rules, all membranes of the system, or the membranes division [8].  It is clear that execution of the P system framework programming on a sequential hardware does not give us a relevant result, unless it is applied on a parallel architecture. Recently, some studies were conducted on the implementation of Membrane Computing on the parallel architecture [30–34]. In all of the studies, the speed execution has been extremely increased.On the other hand, classical search algorithms explore systematically the space of states through the saving of one or more paths in the memory and, then, recording the alternatives existing in each choice point. Once a final state is explored, the path considered as the transitions sequence is known as the solution to the problem. Many of the methods presented are designed specifically for solving the classical search problems. There are different heuristics and approximation algorithms that have found the solution in a reasonable time, but, at the same time, they may be less accurate or even they may have a good accuracy but with an exponential complexity in time [35]. One of these algorithms that have been proposed and designed already is breadth-first search (BFS). Therefore, like the parallel algorithms, few attempts have been made for improving the time complexity of the accurate searching methods.So far, many researches (especially in real life problems) on classical searching have been conducted to reduce time implement and improve speed execution. Li et al. in [36] proposed a new algorithm that can be applied in searching for the multiple longest common subsequences (MLCS). In terms of the speed of the execution, it outperforms the previous leading parallel MLCS algorithm. In [37], the scheduling problem has been studied, in which a modified weight-combination search algorithm and a variable neighborhood search were employed to yield the optimal or near-optimal schedule. The results showed that the obtained solutions were near-optimal solutions in a reasonable computational time. Liu et al. [38], by combination of BFS and depth-first search (DFS) algorithms, obtained two new algorithms; these algorithms are known as memory function maximum degree algorithm (MD) and memory function preference degree algorithm (PD). In these cases, simulation results show that the two algorithms’ performances are excellent at the same time, and the performances are improved at least 10 times. In another study, Shih et al. [39] proposed a new method for development of a splitting-based schema called Merged Search Tree to improve the schema of binary search tree defined in the radio frequency identification (RFID) system. Merged Search Tree method greatly improved the time and power performance simultaneously.In this paper, we propose a new parallel method byP system with division rule through the exploration of  BFS in a binary tree which includes positive integer weight and with finite depth. With this new method, the time complexity will be decreased from exponential to linear time. The paper is organized as follows: Section 2 describes the related works. In Section 3, we presented some basic definitions on P system with division rule. Section 4 introduces the BFS. The proposed method for BSF based on P system with membrane division is presented in Section 5, in which we provided some guidelines of the implementation of P system with membrane division for BFS. In Section 6, using two examples, experiments carried out in this study are presented. Finally, in Section 7, we presented the conclusion, and some ideas for future works were discussed.


## 2. Related Works

The searching problem has been recently studied on the framework of Membrane Computing. A first study on DFS,   was presented by Gutiérrez-Naranjo and  Pérez-Jiménez  [40, 41]; also the first study on local search was presented by Gutiérrez-Naranjo and Pérez-Jiménez [40, 41]. In both cases, the search is done using transition P systems; also N-Queen problem has been considered in these researches as the case study. The results have been compared to N-Queen problem in [42] and to  one  other. The solution presented for 4 queens in [42] was obtained after 20,583 seconds (more than 5 hours). The average time obtained for 20 queens in [40, 41] approaches are 15,944 and 0.133275 seconds, respectively.Also DFS in [43] and BFS in [44] have been studied on disjoint paths using P systems. In the second one, the execution time was improved compared to the first study. In [45], BFS has also been proposed for solving disjoint paths problem using P systems. In this study, the execution time has been improved in comparison with the previous study. In all three cases, the searches were done without division rules.


## 3.P System with Membrane Division

One of the models that have been mostly studied in the field of Membrane Computing is theP system with membrane division, which is well recognized in the P system community. This model is one of the first models introduced in  2001  [8].Definition 1.
AP system with division rule for elementary membranes and with output is a construct of the form, where(1)
m≥1 signifies the initial degreeof the P system;(2)
V denotes the alphabet of symbol-objects;(3)
T⊆V is the output alphabet;(4)
H indicates a finite set of labelsfor membranes;(5)
μ stands for a membrane structure, consisting of m membranes that initially have neutral polarizations labeled with elements of H;(6)
w1,…,wm indicate strings over V, which describe the initial multisetsof the objects placed in the m regions of μ;(7)
i0 determines the output region;(8)
Rstands for a finite set ofrules of the following forms:
(a)
[x→u]hp, for h∈H,p∈{+,-,0},x∈V,u∈V*  (V* is set of strings over V).This is an objectevolution rule that is accompanied with a membrane which is labeled with h,and it depends on the membrane polarity. The empty string is represented by λ∈V*.(b)
x[]hp1→[y]hp2, for h∈H,p1,p2∈{+,-,0},x,y∈V.An object is sent in from the immediate outside region of the membrane with the labelh; at the same time, this object would be changed into another object, and, simultaneously, the membrane polarity can also be changed.(c)
[x]hp1→y[]hp2, for h∈H,p1,p2∈{+,-,0},x,y∈V.Here, an object is sent out from the membrane with the labelh to the immediate outside region. This object, at the same time, changes into another object, and, simultaneously, the membrane polarity can be changed.(d)
[x]hp→y, for h∈H,p∈{+,-,0},x,y∈V.A membrane labeled withh is dissolved in reaction with an object. The skin is never dissolved.(e)
[x]hp1→[y]hp2[z]hp3, for h∈H,p1,p2,p3∈{+,-,0},x,y,z∈V.A membrane by an object could be divided into two membranes with the same label, each of them containing one object (objects may be the same or different). And the polarities of these membranes can be altered.These rules are employed based on the following principles.(1)
All rules are used in aparallel  (we can determine the priority for some rules) and in a maximal manner. At each step, one object of a membrane could be utilized by only one rule that is chosen in a nondeterministic way, but any object that is able to evolve by one rule of any form should do its evolution.(2)
With dissolution of a membrane, its contents (multiset and internal membranes) are left free in the surrounding region.(3)
All objects and membranes that have not been specified in a rule and those that have not evolved remain unchanged to the next step.(4)
Those rules that are associated with the membranes that are labeled withhare utilized for the all copies of this membrane. At one step, a membrane that is labeled with hcould only be subjected to one rule of types (b)–(e), and rule (a) could also be applied with other rules. In this case, our assumption is that the evolution rules of type (a) are used first, and after that, the other types of rules are applied. This process takes only one step to be performed.(5)
The skin membrane could not be divided. Like other membranes, it can have “electrically charge”.Definition 2.
One says that ruleRi has priority (in the strong sense) over rule Rj; if Ri can be applied, then rule Rj cannot be applied. In this case one shows Ri>Rj.Definition 3.
Leti0 be an output membrane (region) of P system Π; one says that i0 is a dynamic output if the P system rules can apply on i0.It should be noticed that in the case ofP systems with division rule, there is an evolution in the membrane structure during the time of computation. This evolution could be obtained not only by declining the number of membranes that may happen due to dissolution operations (rules of type (d)) but also by an increase in the number of membranes by division. It could be an exponential increase in a linear number of steps: by applying a division rule aftern steps, and because of the maximal parallelism, we get 2n copies from the membranes of the same labels. It is an approach that has been mostly investigated to obtain an exponential workspace to reduce the time through increasing the space for solving the computationally hard problems (such as NP-complete problems) in a polynomial or even linear time.


## 4. Breadth-First Search

Searching is based on numerous processes in the artificial intelligence. The most important point is that lots of real-life problems could be settled as a space of states. A state refers to description of the world in a certain instant (expressed in some languages), and two states are linked by a transition if the second state can be reached from the previous one by applying one elementary operation [35].As mentioned above, using this abstraction, the searching methods have been widely studied regardless of the problems arisen in the real world. The studies have been conducted on aspects such as the completeness (where the searching method can find a solution, if any), time and space complexity, and optimality (whether the solution is optimal in some sense). Considering the searching tree, wherein the nodes indicate the states and the arcs represent the transitions, the classical search focuses on the order in which the nodes of the tree should be explored. In this search, there are two possible approaches; in the first instance, the blind search in which the search is guided only by the topology of the tree without any information from the states. In the second instance, the informed search in which some information about the nodes’ characteristics are employed for defining heuristics to determine the next node to be explored.In each time unit of the sequential algorithms, a single node is considered. In this computation framework, the searching strategies are determined through the different orders in which the new nodes are explored. Within a typical framework, several nodes could be possibly explored, and, for continuing the search, we should select one of them. In the best state, there is a heuristic that can be helpful while choosing the best options from the existing candidates. In a certain sense, this heuristic indicates the distance of the considered node from a solution node, and this property provides us with information about the problem nature. In lots of other situations, we cannot have access to any information about this distance, and a blind strategy is required to be applied.Due to the lack of information about the problem nature, the blind strategies are considered exclusively within the topology of the graph (tree) and also in the order where new nodes are reached. The BFS is one of the basic types of the blind search strategies, which expands the nodes in an order regarding to their distance from the root (Figure1(a)). The time complexity for this search strategy is O(bd), where b represents the maximum branching factor and d signifies the lowest depth in which the solution could be found (for more information, see [35]).BFS on binary tree according to classical (a) and proposed (b) methods.
(a)
(b)


## 5. Proposed Method

In this section, we present a first approach to BFS byP systems with membrane division. The goal of this approach is to show that Membrane Computing provides all the ingredients that we need to find a solution for any problem represented as a space of states and, hence, to be a useful tool to solve many real-life problems. In this approach, our aim is looking for a solution in search space (binary tree) by using a P system with membrane division according to BFS.


### 5.1. An Overview of Breadth-First Search byP System with Membrane Division

In this section, we provide the design overview of aP system family with membrane division of searching according to the BFS binary trees with positive integer weight and with finite depth.  The substance of the research is as follows: in initial configuration, the P system explores the root (start state); then, it checks to find the goal (final state), if any. Next, the computation will be halted and the remaining nodes show the path from start to goal. If the goal does not exist, then the P system divides the membranes (elementary membrane that located in the skin), explores the next level (depth) of nodes (Figure 2), and checks again to find the goal (see the proposed method in Figure 3). The computation will be continued until the goal is found. Considering the fact that each level of tree is explored in one stage (Figure 1(b)), and if the goal exists at the depth d, the goal will be discovered after d+1 stages (stage 0 for root, stage 1 for depth 1, and stage dfor depth d).Figure 2
General view of the system.Figure 3
Logical scheme.In Section5.2, it will be demonstrated that each stage takes 4 steps (except stage one), and the time complexity of this method is O(4d+5)=O(d).So the time complexity for BFS at this method will decrease from O(2d) to O(d). On the other hand, we know that one of the challenges that have arisen on the search threads is complexity in time, hence using a P system with membrane division can be a very convenient way for searching with low time complexity. Also, because of the parallel operation of the rules, the time execution will reduce in the P system.


### 5.2. Breadth-First Search Problem Formulation andP System Structure

In this section, we consider aP system with membrane division for BFS on binary trees and explain their features according to Section 5.1. We illustrate the rules and their implementation, step by step. It is noticeable that each binary tree’s node has four fields: a key node, parent pointer, left child pointer, and right child pointer. The key node is the label or weight of a node, and pointers are the interface between the parent, the left and right children nodes. With this brief introduction, we explain the case study tree that considers the random binary tree with the following features.(i)
Depth of tree is integer numbern, where n≥0;(ii)
the nodej is shown by aj;(iii)
the left and right child pointers foraj are 2j and 2j+1, respectively;(iv)
the key node foraj is xj∈N, we show key(aj)=xj;(v)
the key node for final state (goal) isG, we show key (goal) =G;(vi)
the relationship betweenaj and its parent is considered by
(1)yj,yj={1,if there existaj0,if there exist notaj;(vii)
the numerical inputs of system aren,G,xj, and yj.Note that in all of above relations1≤j≤2n+1-1.We also define theP system structure as follows.We will considerP system Π=(V,H,Γ,µ,w0,w1,R1,R2,1,R2,2,R3,1,R3,2,R4,1,R4,2,R5,R6,1) with dynamic output i0=1 and with the strong priorities R3.1>R4.1>R5, where(i)
the working alphabetV={k,t,y,z}∪{aj,bj,cj∣1≤j≤2n+1-1};(ii)
the output alphabetΓ={aj∣1≤j≤2n+1-1};(iii)
the set of labelsH={0,1};(iv)
the initial membrane structureμ=[[]10]00;(v)
the initial multisetsw0= and w1={c1}.We also consider the set of rulesR as follows:
(2)R1≡[y⟶z2n]00.
This rule produces 2n copies of z by y in membrane 0 (skin);
(3)R2≡{(1)z[]10⟶[z]1+(2)[z]1+⟶λ.
Using these rules, the membrane with label 1 is recharged and dissolved; these rules are applied when the answer is obtained, and computation halts
(4)R3≡{(1)[t]10⟶t[]1+(2)[t⟶λ]1+.
After applying these rules, a copy of t will be sent to outside and the charge of membrane is changed; after that, all copies of t disappeared, in membrane 1 with positive charge
(5)R4≡{(1)[k]10⟶y[]1-(2)[k]1+⟶[]10.
In first case, object k changes the charge of membrane 1 from neutral to negative and sends object yout of membrane; at the same time, k disappeared. This rule will be applied when there is no any object of t in membrane 1 with neutral charge (see R3), and it means that the answer is here (see R6). In the second case, k changed the charge of membrane 1 from positive to neutral, and the process is ready to continue
(6)R5≡[bj]10⟶[c2j]10[c2j+1]10,1≤j≤2n-1.
Object bj divides membrane 1 and sends c2j and c2j+1 to core of each new membrane, that they produce the children of current parent’s node in the next step. If node j is nil, then yj=0, and, in the next step, node aj will not be produced. If node aj is not nil, thenyj=1, and, in next step, node aj will be produced:
(7)R6≡[cj⟶t(G-xj)2aj(bj)yjk]10,1≤j≤2n+1-1.
From cj, rules R6 makes aj, (bj)yj, k, and some copies of t, among them, aj is a current node. If yj=1, then we have one copy bj, and it makes the properties of aj’s children in the next step (see R5). If yj=0, then the computation in this branch will be stopped. The appearance of t means that the goal (G) is not yet reached; therefore, rule R3 is applied and the process will continue. If there is any copy of t, it means that the goal is reached; therefore, rule R4.1 is applied and the process will be stopped after applying rules R1 and R2.Remark 4.
We denote theP system Π configuration in step i by Ci, and C0 is initial configuration.Remark 5.
We consider a path from root until nodeain in a binary tree with depth, by ai0ai1…aimai(m+1)…ain=Ain, where 2m≤im≤2m+1-1,  0≤m≤n,  i(m+1)=2(im)ori(m+1)=2(im)+1.Lemma 6.
Let be a nonnegative integer number, and be natural numbers, and letyj=1 and G≠xj, where  2i≤j≤2i+1-1 and 0≤i≤n. If Π is the P system mentioned above, then there exist 2i membranes with label 1 and neutral charge including a multiset in the form t(G-xj)2  Ajbjk in configuration C4i+1.Proof.
We will prove the lemma by induction oni.
Case  1(i=0). In initial configuration (C0), there exists only object c1 in P system that is located inside membrane 1 with neutral charge. Therefore, in step one, the rules of type R6 will be applied, object c1 is changed into t(G-x1)2a1b1k=t(G-x1)2A1b1k, and thus the proposition is true for i=0.
Case  2
(
i
<
n
→
i
+
1
). Let i be such that 0≤i<n, by inductive hypothesis, there exist 2i membranes with label 1 and neutral charge including a multiset in the form t(G-xj)2Ajbjk in configuration C4i+1. In this configuration, if (G-xj)2=1, then rule R3.1 will be applied (rules R3.1,R4.1, and R5 can be applied on objects t, k, and bj, respectively, but with this order R3.1>R4.1>R5) in step 4i+2, and this rule changes the polarization of membranes 1 from neutral to positive. After that, in step 4i+3, rule R4.2 will be applied, and it changes the polarization of membranes 1 from positive to neutral. If (G-xj)2>1, then rule R3.1 will be applied in step 4i+2; after that, rules R3.2 and R4.2 will be applied simultaneously (see Section 3,  principal 4)  and C4i+3 will be obtained. In both conditions, k and t will disappear and we obtain 2i membranes with label 1 and neutral charge, and each membrane  includes  a multiset in the form Ajbj. Now rules R5  is  applied in step 4i+4 and each membrane will be duplicated; half of them include Ajc2j(1), and the remaining include Ajc2j+1(2). Therefore, we have 2i+1 membranes with label 1 and neutral  charge; each of them includes  one multiset such as (1) or (2). In step 4i+5, rules R6 will be applied and multisetsAjc2j andAjc2j+1will be changed to t(G-x2j)Aja2jb2jk and t(G-x2j+1)Aja2j+1b2j+1k, respectively. On the other hand, we know that Aja2j=A2j and Aja2j+1=A2j+1; then, in step 4i+5=4(i+1)+1, we have 2i+1 membranes with label 1 and neutral charge, and each membrane includes one multiset in the form  t(G-xJ)AJbJk, where2i+1≤J≤2i+2-1. Thus, the proposition is true for all numbers i, where0≤i≤n,  and, in configuration C4i+1, there exist 2i membranes with label 1 and neutral charge, and each membrane includes a multiset in the form t(G-xj)2Ajbjk.Note. According to Lemma 6, if there is not any goal, computations will continue to depth n.Lemma 7.
If the assumptions to Lemma6 are satisfied, then for each j, there exists a membrane with label 1 and neutral charge, including Aj in configuration C4i+1.Proof.
It is evident according to the definition ofAj, there exist 2i copies of Aj  (2i≤j≤2i+1-1,1≤i≤n); also according to Lemma 6, in configuration C4i+1 there exist 2i membranes with label 1 and neutral charge, including a multiset in the form t(G-xj)2Ajbjk, and thus the lemma holds for each j.Theorem 8.
The BFS can be implemented on a binary tree by aP system with division rule in a linear time.Proof.
Let the goal be located in the nearest depthd; it means there exists at least a j,  2d≤j≤2d+1-1 such that G=xj and G≠xj, for all j  (2i≤j≤2i+1-1,i<d). We consider a P system and a complete binary tree (yi=1,1≤i≤2n+1-1) according to assumptions presented in Lemma 6 and Aj according to Remark 5 (Aj is the path from root until node aj). By Lemmas 6 and 7 the whole of paths from root until depth d are explored in configuration C4d+1. Hence, in step 4d+1, one of membranes (perhaps more than one) with neutral charge includes just Ajbjk (there is no t; it means that the goal is here and Aj shows the path from root until goal). We consider this membrane with label 1′. Next, in step 4d+2, for membrane 1′, rule R4.1 and for membranes 1, rule R3.1 will be applied simultaneously. In this case, object k changes the polarization of membrane 1′, and it sends an object y out of the membranes and disappears, simultaneously. In this moment, membrane 1′ has the negative polarization, so any rules cannot be applied on it. Also in step 4d+2, object t changes the polarization of membranes 1 from neutral to positive charge. In step 4d+3, each object y evolves to z2n in membrane 0 by rule R1, and, at the same time, object t will be dissolved in membranes 1 by rule R3.2, and object k will be sent out of membranes 1 and changes the polarization of membrane from positive to neutral charge by rule R4.2. The rules apply maximally parallel manner. In step 4d+4, one copy of object z that have been produced in step 4d+3 will be sent to each membrane with label 1, and the polarization will be changed from neutral to positive by applying rule R2.1. In step 4d+5 (the last step), object z dissolves membranes 1, and the computation will be halted. Finally, membrane (perhaps some membrane) with label 1 (1′) will be remained with negative charge that shows the place of the goal by the path (multiset Ajbj) that is located in each membrane. Therefore, the presented P system explores a complete binary tree according to BFS method in a linear time. It is clear that even if the tree is not complete, the theorem is true.


## 5.1. An Overview of Breadth-First Search byP System with Membrane Division

In this section, we provide the design overview of aP system family with membrane division of searching according to the BFS binary trees with positive integer weight and with finite depth.  The substance of the research is as follows: in initial configuration, the P system explores the root (start state); then, it checks to find the goal (final state), if any. Next, the computation will be halted and the remaining nodes show the path from start to goal. If the goal does not exist, then the P system divides the membranes (elementary membrane that located in the skin), explores the next level (depth) of nodes (Figure 2), and checks again to find the goal (see the proposed method in Figure 3). The computation will be continued until the goal is found. Considering the fact that each level of tree is explored in one stage (Figure 1(b)), and if the goal exists at the depth d, the goal will be discovered after d+1 stages (stage 0 for root, stage 1 for depth 1, and stage dfor depth d).Figure 2
General view of the system.Figure 3
Logical scheme.In Section5.2, it will be demonstrated that each stage takes 4 steps (except stage one), and the time complexity of this method is O(4d+5)=O(d).So the time complexity for BFS at this method will decrease from O(2d) to O(d). On the other hand, we know that one of the challenges that have arisen on the search threads is complexity in time, hence using a P system with membrane division can be a very convenient way for searching with low time complexity. Also, because of the parallel operation of the rules, the time execution will reduce in the P system.


## 5.2. Breadth-First Search Problem Formulation andP System Structure

In this section, we consider aP system with membrane division for BFS on binary trees and explain their features according to Section 5.1. We illustrate the rules and their implementation, step by step. It is noticeable that each binary tree’s node has four fields: a key node, parent pointer, left child pointer, and right child pointer. The key node is the label or weight of a node, and pointers are the interface between the parent, the left and right children nodes. With this brief introduction, we explain the case study tree that considers the random binary tree with the following features.(i)
Depth of tree is integer numbern, where n≥0;(ii)
the nodej is shown by aj;(iii)
the left and right child pointers foraj are 2j and 2j+1, respectively;(iv)
the key node foraj is xj∈N, we show key(aj)=xj;(v)
the key node for final state (goal) isG, we show key (goal) =G;(vi)
the relationship betweenaj and its parent is considered by
(1)yj,yj={1,if there existaj0,if there exist notaj;(vii)
the numerical inputs of system aren,G,xj, and yj.Note that in all of above relations1≤j≤2n+1-1.We also define theP system structure as follows.We will considerP system Π=(V,H,Γ,µ,w0,w1,R1,R2,1,R2,2,R3,1,R3,2,R4,1,R4,2,R5,R6,1) with dynamic output i0=1 and with the strong priorities R3.1>R4.1>R5, where(i)
the working alphabetV={k,t,y,z}∪{aj,bj,cj∣1≤j≤2n+1-1};(ii)
the output alphabetΓ={aj∣1≤j≤2n+1-1};(iii)
the set of labelsH={0,1};(iv)
the initial membrane structureμ=[[]10]00;(v)
the initial multisetsw0= and w1={c1}.We also consider the set of rulesR as follows:
(2)R1≡[y⟶z2n]00.
This rule produces 2n copies of z by y in membrane 0 (skin);
(3)R2≡{(1)z[]10⟶[z]1+(2)[z]1+⟶λ.
Using these rules, the membrane with label 1 is recharged and dissolved; these rules are applied when the answer is obtained, and computation halts
(4)R3≡{(1)[t]10⟶t[]1+(2)[t⟶λ]1+.
After applying these rules, a copy of t will be sent to outside and the charge of membrane is changed; after that, all copies of t disappeared, in membrane 1 with positive charge
(5)R4≡{(1)[k]10⟶y[]1-(2)[k]1+⟶[]10.
In first case, object k changes the charge of membrane 1 from neutral to negative and sends object yout of membrane; at the same time, k disappeared. This rule will be applied when there is no any object of t in membrane 1 with neutral charge (see R3), and it means that the answer is here (see R6). In the second case, k changed the charge of membrane 1 from positive to neutral, and the process is ready to continue
(6)R5≡[bj]10⟶[c2j]10[c2j+1]10,1≤j≤2n-1.
Object bj divides membrane 1 and sends c2j and c2j+1 to core of each new membrane, that they produce the children of current parent’s node in the next step. If node j is nil, then yj=0, and, in the next step, node aj will not be produced. If node aj is not nil, thenyj=1, and, in next step, node aj will be produced:
(7)R6≡[cj⟶t(G-xj)2aj(bj)yjk]10,1≤j≤2n+1-1.
From cj, rules R6 makes aj, (bj)yj, k, and some copies of t, among them, aj is a current node. If yj=1, then we have one copy bj, and it makes the properties of aj’s children in the next step (see R5). If yj=0, then the computation in this branch will be stopped. The appearance of t means that the goal (G) is not yet reached; therefore, rule R3 is applied and the process will continue. If there is any copy of t, it means that the goal is reached; therefore, rule R4.1 is applied and the process will be stopped after applying rules R1 and R2.Remark 4.
We denote theP system Π configuration in step i by Ci, and C0 is initial configuration.Remark 5.
We consider a path from root until nodeain in a binary tree with depth, by ai0ai1…aimai(m+1)…ain=Ain, where 2m≤im≤2m+1-1,  0≤m≤n,  i(m+1)=2(im)ori(m+1)=2(im)+1.Lemma 6.
Let be a nonnegative integer number, and be natural numbers, and letyj=1 and G≠xj, where  2i≤j≤2i+1-1 and 0≤i≤n. If Π is the P system mentioned above, then there exist 2i membranes with label 1 and neutral charge including a multiset in the form t(G-xj)2  Ajbjk in configuration C4i+1.Proof.
We will prove the lemma by induction oni.
Case  1(i=0). In initial configuration (C0), there exists only object c1 in P system that is located inside membrane 1 with neutral charge. Therefore, in step one, the rules of type R6 will be applied, object c1 is changed into t(G-x1)2a1b1k=t(G-x1)2A1b1k, and thus the proposition is true for i=0.
Case  2
(
i
<
n
→
i
+
1
). Let i be such that 0≤i<n, by inductive hypothesis, there exist 2i membranes with label 1 and neutral charge including a multiset in the form t(G-xj)2Ajbjk in configuration C4i+1. In this configuration, if (G-xj)2=1, then rule R3.1 will be applied (rules R3.1,R4.1, and R5 can be applied on objects t, k, and bj, respectively, but with this order R3.1>R4.1>R5) in step 4i+2, and this rule changes the polarization of membranes 1 from neutral to positive. After that, in step 4i+3, rule R4.2 will be applied, and it changes the polarization of membranes 1 from positive to neutral. If (G-xj)2>1, then rule R3.1 will be applied in step 4i+2; after that, rules R3.2 and R4.2 will be applied simultaneously (see Section 3,  principal 4)  and C4i+3 will be obtained. In both conditions, k and t will disappear and we obtain 2i membranes with label 1 and neutral charge, and each membrane  includes  a multiset in the form Ajbj. Now rules R5  is  applied in step 4i+4 and each membrane will be duplicated; half of them include Ajc2j(1), and the remaining include Ajc2j+1(2). Therefore, we have 2i+1 membranes with label 1 and neutral  charge; each of them includes  one multiset such as (1) or (2). In step 4i+5, rules R6 will be applied and multisetsAjc2j andAjc2j+1will be changed to t(G-x2j)Aja2jb2jk and t(G-x2j+1)Aja2j+1b2j+1k, respectively. On the other hand, we know that Aja2j=A2j and Aja2j+1=A2j+1; then, in step 4i+5=4(i+1)+1, we have 2i+1 membranes with label 1 and neutral charge, and each membrane includes one multiset in the form  t(G-xJ)AJbJk, where2i+1≤J≤2i+2-1. Thus, the proposition is true for all numbers i, where0≤i≤n,  and, in configuration C4i+1, there exist 2i membranes with label 1 and neutral charge, and each membrane includes a multiset in the form t(G-xj)2Ajbjk.Note. According to Lemma 6, if there is not any goal, computations will continue to depth n.Lemma 7.
If the assumptions to Lemma6 are satisfied, then for each j, there exists a membrane with label 1 and neutral charge, including Aj in configuration C4i+1.Proof.
It is evident according to the definition ofAj, there exist 2i copies of Aj  (2i≤j≤2i+1-1,1≤i≤n); also according to Lemma 6, in configuration C4i+1 there exist 2i membranes with label 1 and neutral charge, including a multiset in the form t(G-xj)2Ajbjk, and thus the lemma holds for each j.Theorem 8.
The BFS can be implemented on a binary tree by aP system with division rule in a linear time.Proof.
Let the goal be located in the nearest depthd; it means there exists at least a j,  2d≤j≤2d+1-1 such that G=xj and G≠xj, for all j  (2i≤j≤2i+1-1,i<d). We consider a P system and a complete binary tree (yi=1,1≤i≤2n+1-1) according to assumptions presented in Lemma 6 and Aj according to Remark 5 (Aj is the path from root until node aj). By Lemmas 6 and 7 the whole of paths from root until depth d are explored in configuration C4d+1. Hence, in step 4d+1, one of membranes (perhaps more than one) with neutral charge includes just Ajbjk (there is no t; it means that the goal is here and Aj shows the path from root until goal). We consider this membrane with label 1′. Next, in step 4d+2, for membrane 1′, rule R4.1 and for membranes 1, rule R3.1 will be applied simultaneously. In this case, object k changes the polarization of membrane 1′, and it sends an object y out of the membranes and disappears, simultaneously. In this moment, membrane 1′ has the negative polarization, so any rules cannot be applied on it. Also in step 4d+2, object t changes the polarization of membranes 1 from neutral to positive charge. In step 4d+3, each object y evolves to z2n in membrane 0 by rule R1, and, at the same time, object t will be dissolved in membranes 1 by rule R3.2, and object k will be sent out of membranes 1 and changes the polarization of membrane from positive to neutral charge by rule R4.2. The rules apply maximally parallel manner. In step 4d+4, one copy of object z that have been produced in step 4d+3 will be sent to each membrane with label 1, and the polarization will be changed from neutral to positive by applying rule R2.1. In step 4d+5 (the last step), object z dissolves membranes 1, and the computation will be halted. Finally, membrane (perhaps some membrane) with label 1 (1′) will be remained with negative charge that shows the place of the goal by the path (multiset Ajbj) that is located in each membrane. Therefore, the presented P system explores a complete binary tree according to BFS method in a linear time. It is clear that even if the tree is not complete, the theorem is true.


## 6. Experimental Simulation

We will give some hints on the computation by following the computation of the examples that were shown in Figures4(a) and 4(b).Binary random trees with positive integer weights.
(a)
(b)Example 9.
Let us find number 6 in the tree according to Figure4(a).  Therefore n=4,G=6,and you can see the weights on the tree. In configuration C0, there is just one object c1 that occurs in membrane 1; therefore, for the first time, rules R6 is applied and we achieve t25a1b1k in membrane 1 for configuration C1. Next, rule R3.1 and after that R3.2 and R4.2 are applied (R3.2 and R4.2 are applied simultaneously), objects t and k will be dissolved (obtaining C3), and the system will be ready to continue; then we can apply rules R5 (obtaining C4) in the next step. This is the first time that we divide membrane 1, so there are two membranes with label 1 in C4 in which one of them contains a1c2 and another one contains a1c3. In step (5), rules R6 can be applied and multisets are changed to t16a1a2b2k and t9a1a3b3k.Now the computation will be repeated as above. Therefore, inC13, we have eight membranes with label 1 and neutral charge that each one contains one of the multisets t9a1a2a4a8b8k, t16a1a2a4a9b9k, t25a1a2a5a10b10k, t4a1a2a5a11b11k, a1a3a6a12b12k,t25a1a3a6a13b13k,t16a1a3a7a14b14k,  or  t9a1a3a7a15b15k. In the next step, two rules are applied at the same time, R3.1 and R4.1, and C14  is obtained. Rule R4.1 is applied on membrane that contains multiset a1a3a6a12b12k (goal is here); this rule makes k disappear, makes one copy of y in region 0, and changes the polarization of the membranes from neutral to negative charge, but R3.1 is applied on other membranes and changes their charge from neutral to positive charge. C15 will be obtained after applying rules R1,R3.2, and R4.2, simultaneously. In this case, objects t are dissolved by R3.2, and, by applying rule R4.2 on the whole membranes, the charges will be changed from positive to neutral, except the membrane containing multiset a1a3a6a12b12  and  has negative charge; also there will be 24 copies of z by applying rule R1. After applying rules R2.1 and R2.2, all of the membranes will be dissolved, except for the membrane containing a1a3a6a12b12 with negative charge; we achieve C17, and computation is halted. It can be seen that the path for searching from start (root) to the goal in the membrane remained a1a3a6a12. In addition, it can be seen also that the brief of computation in Figure 5 shows paths’ multisets.Figure 5
An overview of proposedP system process for searching number 6.For verification, we run the program in an updated version of the P-Lingua [46]. The final configuration (configuration 17) is shown by P-Lingua simulator in Figure 6.Figure 6
The final configuration of the search tree by P-Lingua simulator of the proposed method for finding number 6 and its path from start (root) until goal (number 6) located in membrane with label 1 and neutral charge.Example 10.
Let us find number 7 in the tree shown in Figure4(b).  Therefore, n=4,G=7, and you can see the weights on the tree. This tree is not complete and there are 4 goals in depth 4, the proposed method can find all of the goals. The simulation is carried out using P-Lingua shown in Figure 7.Figure 7
The final configuration of the search tree by P-Lingua simulator of the proposed method for finding number 7 and its paths from start (root) until goals (number 7) located in membranes with label 1 and neutral charge.


## 7. Conclusion and Future Works

Due to the high computational cost, many classical methods have exponential time complexity. Since breadth-first search is one of these cases, for searching solution to real-life hard problems, it is very important to decrease time complexity. The proposed method has been successful in decreasing the time complexity.UsingP system with membrane division, this study presents an advanced approach to find a solution to the problem of breadth-first search. An exponential workspace has been created to decrease the time complexity from an exponential to a linear time. For the future studies, it is recommended to improve the design from the P system aspect that may include new ingredients and polynomial or linear uniform. Another recommendation is to conduct new case studies that are more connected with  real-life problems. A study can be carried out on the implementation of this design on one parallel architecture and compare the results with the obtained  ones  from a sequential architecture.



---

*Source: 424108-2013-05-20.xml*