# Fraction Reduction in Membrane Systems

Authors: Ping Guo; Hong Zhang; Haizhu Chen; Ran Liu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Fraction reduction is a basic computation for rational numbers. P system is a new computing model, while the current methods for fraction reductions are not available in these systems. In this paper, we propose a method of fraction reduction and discuss how to carry it out in cell-like P systems with the membrane structure and the rules with priority designed. During the application of fraction reduction rules, synchronization is guaranteed by arranging some special objects in these rules. Our work contributes to performing the rational computation in P systems since the rational operands can be given in the form of fraction.


---

## Body

## 1. Introduction

Membrane computing (also called P systems) is a branch of natural computing introduced by Pǎun in 1998 which abstracts computing models from the architecture and the functioning of living cells [1]. Membrane computing model takes the living cell as multihierarchical structural regions which are referred to as the membranes [2]. In the compartments defined by membranes there are objects that can evolve to other objects and pass through the membranes. After Pǎun proposed and proved that P systems based on membrane division can solve SAT problems in polynomial time [3], many variants of P systems, including cell-like [4, 5], tissue-like [6], and neural-like ones [7], have been successfully used to design solutions for NP-complete problems. The introductions of the complexity, parallelism, decomposition of membrane, and hierarchical structure can be found in [8, 9].Based on cell-like P systems which are one kind of common systems in membrane computing, Atanasiu firstly constructs arithmetic P systems to implement arithmetic operations [10]. Reference [11] designs multilayer P systems without priority rules to lower the complexity of the operations. And, in [12], the membrane structure is simplified greatly and efficiency of the computations is also improved owing to arithmetic operations being performed in a single membrane without priority rules. Furthermore, multimembrane P systems are constructed for signed arithmetic operations [13] and the operational range of P system can be extended to the whole integer field. In [14] arithmetic expression is evaluated with primary arithmetical operations implemented in single membranes. Reference [15] proposes an algorithm and builds expression P systems without priority rules for evaluating arithmetic expression. And [16] implements primary arithmetic operations of fractions in P systems and builds a bridge between rational numbers and membrane computing. In cell-like P systems, the operands of the arithmetic operations are represented by multiset, which is composed by the objects and their cardinalities. The rational number can be given by the form of fraction, whose numerator and denominator can be represented by multisets, respectively, so the fraction can be a bridge for implementing the calculations of the rational numbers in P systems.However, [16] has not further processed the computation results which need to be reduced to lighten the load of the subsequent fraction computations. This paper proposes a suitable method of fraction reduction and implements it in P systems. The rest of this paper is organized as follows: Section 2 introduces cell-like P systems, and Section 3 proposes and proves the fraction reduction method. In Section 4, based on cell-like P system, the rules for implementing fraction reduction are described in detail with the membrane structure designed. The conclusions are drawn in the final section.


## 2. Foundations

### 2.1. Cell-Like P Systems

Our work in this paper is based on cell-like P systems, and such system (of degreem≥1) can be defined formally as [1, 2]
(1)Π=(O,μ,ω1,…,ωm,R1,…,Rm,ρ1,…,ρm,io),
where(i)
Ois the alphabet of the system. Each symbol represents one kind of object. O* is the finite and nonempty multiset over O where λ is empty string; O+=O*-{λ};(ii)
μ is a membrane structure with m membrane, labeled by 1,2,…,m;(iii)
ωi(1≤i≤m) is string over O representing the multiset of objects placed in membrane i. For example, there are 5 copies of object a and 3 copies of object b in membrane i; then we have ωi=a5b3; ωi=λ means that there is no object in membrane i;(iv)
io is output region of the system and it saves the final results;(v)
R1,R2,…,Rm are finite sets of possible evolution rules over O associated with the regions 1,2,…,m of μ. The rules in Ri (1≤i≤m) are of the form U→V|a, with a∈O, U∈O+, V=(V′,ξ), or V=(V′,ξ)δ, V′∈O* and ξ={here,out,inj∣1≤j≤m}: here means the product V′ remains in the same region; out means V′ goes out of the region and enters into another membrane which includes membrane i as its submembrane; and inj means V′ goes into membrane j which is a submembrane of membrane i. Specifically, when ξ=here,(V′,ξ) can be abbreviated as V′. δ is a special symbol not in O, and it means that the membrane which includes it will be dissolved and the contents of this membrane will be left in the outer membrane. Object a is a promoter in the rule U→V|a; this rule can only be applied in the presence of object a;(vi)
ρi (1≤i≤m) defines a partial order relation among the rules in Ri. If ρi={a→b>c→d} and both objects a and c are available, then only a→b can be applied although the two rules do not compete for any objects.Beside the above rules, we also consider rules for membrane creation, which is of the forme→[Vi]i, with e∈O, V∈O*, and i is a number from a given list of the labels; the idea is that the object e creates a new membrane labeled by i, including multiset V and associated with evolution rules [17].In each membrane, rules are applied according to the following principles.(i)
Nondeterminism. Supposen rules compete for the reactants which can only support m(m<n) rules to be applied; then the m rules are chosen nondeterministically.(ii)
Maximal parallelism. All of the rules that can be applied must be applied simultaneously.From now on we only deal with cell-like P systems with membrane creation and call them P systems for brevity.


### 2.2. Fraction Arithmetic Operations

Reference [16] discusses how to perform fraction arithmetic operations by P systems based on multiple membranes. In [16], the fraction arithmetical operations are written in the form as
(2)(+/-)m1m2op(+/-)n1n2,op∈{+,-,×,÷},
where m1, m2, n1, and n2 are all integers; m2>0, n2>0, m1≥0, and n1≥0.Fraction operands are converted into the format which the integer arithmetic requires when the operation is processed. The process of initialization makes the fraction operand be represented in a unified form and it simplifies the operation rules since different operands can be represented by the same objects in the P systems. After initialization, [16] designs four kinds of fraction arithmetic P systems to implement primary arithmetic operations of fractions (namely, addition, subtraction, multiplication, and division).The computation results obtained by the systems in [16] are not in reduced form. So they are required to be processed further for lightening the load of the subsequent fraction computations. However, the current methods for fraction reductions are not available in P systems. In this paper, we propose a method of fraction reduction and discuss how to carry it out in cell-like P systems.


## 2.1. Cell-Like P Systems

Our work in this paper is based on cell-like P systems, and such system (of degreem≥1) can be defined formally as [1, 2]
(1)Π=(O,μ,ω1,…,ωm,R1,…,Rm,ρ1,…,ρm,io),
where(i)
Ois the alphabet of the system. Each symbol represents one kind of object. O* is the finite and nonempty multiset over O where λ is empty string; O+=O*-{λ};(ii)
μ is a membrane structure with m membrane, labeled by 1,2,…,m;(iii)
ωi(1≤i≤m) is string over O representing the multiset of objects placed in membrane i. For example, there are 5 copies of object a and 3 copies of object b in membrane i; then we have ωi=a5b3; ωi=λ means that there is no object in membrane i;(iv)
io is output region of the system and it saves the final results;(v)
R1,R2,…,Rm are finite sets of possible evolution rules over O associated with the regions 1,2,…,m of μ. The rules in Ri (1≤i≤m) are of the form U→V|a, with a∈O, U∈O+, V=(V′,ξ), or V=(V′,ξ)δ, V′∈O* and ξ={here,out,inj∣1≤j≤m}: here means the product V′ remains in the same region; out means V′ goes out of the region and enters into another membrane which includes membrane i as its submembrane; and inj means V′ goes into membrane j which is a submembrane of membrane i. Specifically, when ξ=here,(V′,ξ) can be abbreviated as V′. δ is a special symbol not in O, and it means that the membrane which includes it will be dissolved and the contents of this membrane will be left in the outer membrane. Object a is a promoter in the rule U→V|a; this rule can only be applied in the presence of object a;(vi)
ρi (1≤i≤m) defines a partial order relation among the rules in Ri. If ρi={a→b>c→d} and both objects a and c are available, then only a→b can be applied although the two rules do not compete for any objects.Beside the above rules, we also consider rules for membrane creation, which is of the forme→[Vi]i, with e∈O, V∈O*, and i is a number from a given list of the labels; the idea is that the object e creates a new membrane labeled by i, including multiset V and associated with evolution rules [17].In each membrane, rules are applied according to the following principles.(i)
Nondeterminism. Supposen rules compete for the reactants which can only support m(m<n) rules to be applied; then the m rules are chosen nondeterministically.(ii)
Maximal parallelism. All of the rules that can be applied must be applied simultaneously.From now on we only deal with cell-like P systems with membrane creation and call them P systems for brevity.


## 2.2. Fraction Arithmetic Operations

Reference [16] discusses how to perform fraction arithmetic operations by P systems based on multiple membranes. In [16], the fraction arithmetical operations are written in the form as
(2)(+/-)m1m2op(+/-)n1n2,op∈{+,-,×,÷},
where m1, m2, n1, and n2 are all integers; m2>0, n2>0, m1≥0, and n1≥0.Fraction operands are converted into the format which the integer arithmetic requires when the operation is processed. The process of initialization makes the fraction operand be represented in a unified form and it simplifies the operation rules since different operands can be represented by the same objects in the P systems. After initialization, [16] designs four kinds of fraction arithmetic P systems to implement primary arithmetic operations of fractions (namely, addition, subtraction, multiplication, and division).The computation results obtained by the systems in [16] are not in reduced form. So they are required to be processed further for lightening the load of the subsequent fraction computations. However, the current methods for fraction reductions are not available in P systems. In this paper, we propose a method of fraction reduction and discuss how to carry it out in cell-like P systems.


## 3. A Method for Fraction Reduction

The goal of fraction reduction is to obtain the simplest fraction, and it means the numerator and denominator are coprimes. Generally, fractions can be reduced by the following methods.(i)
Numerator and denominator are divided by the prime factors that they share until their common factor is 1.(ii)
Numerator and denominator are divided directly by their greatest common factor.These two methods are simple, but both of them are not suitable for being implemented in P systems owing to the following.(i)
For the first one, we need to enumerate the primes, such as 2, 3, 5,7,…, to find out the common prime factors of the numerator and denominator. This method involves large calculation and cannot be processed in parallel. If it is implemented in P system, a rule or several rules should be designed for testing whether a prime is their common factor. It means that the more prime factors they share, the more rules are designed and the more complex membrane structure is.(ii)
For the second one, the greatest common factor of the numerator and denominator should be calculated by Euclidean algorithm, but it cannot be performed efficiently in P systems.For designing a set of generally universal rules to implement fraction reduction in P systems, we present a new fraction reduction method, based on which the designed system works independently on the size of the input. In this section, some theories on the new method are given and the corresponding algorithm is proposed subsequently with its correctness ensured by the present theories.


### 3.1. The Principles for Fraction Reduction

Assume that we have integersm, n (0<n<m) and let n0=m, n1=n, the sequences {ai}, {ni}, and {ki} can be constructed as
(3)ai=nini-1=1ki+(ni+1/ni),0≤ni+1<ni,i≥1,
where, for i≥1,
(4)ki=ni-1div⁡ni,ni+1=ni-1mod⁡ni.
For {n0,n1,…,nρ}, we have the following.Theorem 1.
Integer sequence{n0,n1,…,nρ} is monotone decreasing, and there is an integer v>0, such that nv=0.Proof.
(i) Obviously,{n0,n1,…,nρ} is monotone decreasing according to the procedure of the construction.
(ii) Assume thatnt is the minimum in {n0,n1,…,nρ} and nt>0. From the construction, we have
(5)nt+1=nt-1mod⁡nt.
It is easy to see that0≤nt+1<nt. According to the assumption, we obtain nt+1=0 and let v=t+1, namely, nv=0.From (3), we have
(6)at=ntnt-1=1kt+(nt+1/nt)=1kt,ai=1ki+ai+1,0≤i<t-1.The sequence{fi} can be constructed as follows:
(7)ft+1=1,ft=kt,ft-1=kt-1×ft+1.Generally,(8)fi=ki×fi+1+fi+2,1≤i<t-2.So,(9)at=1ft,at-1=1kt-1+at=1kt-1+(1/ft)=ftkt-1×ft+1=ftft-1,at-2=1kt-2+at-1=1kt-2+(ft/ft-1)=ft-1kt-2×ft-1+ft=ft-1ft-2.Generally, for0<i<t,
(10)ai=1ki+ai+1=1ki+(fi+2/fi+1)=fi+1ki×fi+1+fi+2=fi+1fi.Specifically,(11)a1=1k1+a2=f2k1×f2+f3=f2f1.Theorem 2.
f
1 and f2 are coprimes, and f2/f1 is the simplest proper fraction of n/m.Proof.
letξ be the common factor of f1 and f2. According to the construction of {fi}, we can obtain f1=k1×f2+f3, so ξ is also the factor of f3. Similarly, ξ is the common factor of ft-1 and ft. It means that there are ξ1 and ξ2, such that ft-1=ξ×ξ1 and ft=ξ×ξ2. According to the definition of ft-1, we have
(12)ft-1=ξ×ξ1=kt-1×(ξ×ξ2)+1.
That is,
(13)ξ×(ξ1-kt-1×ξ2)=1.
Namely, ξ is the factor of 1. Hence, ξ=1. So f1 and f2 are coprimes.
According to the construction of{ai} and (11), we have f2/f1=a1=n/m, so f2/f1 is the simplest proper fraction of n/m.The proofs of the above theories show that the proposed method is feasible for fraction reduction; namely, the simplest proper fraction can be obtained by this method for any fraction.


### 3.2. The Algorithm for Fraction Reduction

Assume that we want to reduce the fractionn/m (0<n<m); from the discussion in Section 3.1, the procedure for fraction reduction can be described as follows:(i)
inputn, m(0<n≤m);(ii)
compute{ni}, {ki}, i=2,3,…u, and n1=n, n0=m;(iii)
compute{fi}, i=t,t-1,…,1;(iv)
outputf1,f2.We can present an algorithm for fraction reduction in Algorithm1.Algorithm 1:Fraction reduction.
Input: n, m(m≥n>0);
Output:  f1,f2 (f2/f1 is the simplest proper fraction of n/m);
Procedure:
//calculate{ni}, {ki}
i←1;
n1←n, n0←m;
repeat
ki←ni-1div⁡ni;
ni+1←ni-1mod⁡ni;
i←i+1;
untilni+1=0;
//calculate{fi};
i←i-1;
fi+1←1;
fi←ki;
whilei>1  {
fi-1←ki-1*fi+fi+1;
i←i-1;
}
End.In this algorithm, the complexity of the algorithm isO(1) when m is a multiple of the n. Generally, for sequence {ni}, we know nt+1=0 if the algorithm performs mod operation for t times. Comparing sequence {ni} with Fibonacci sequence {Fi}, we have F0=1≤nt and F1=1≤nt-1. And nk≥nk+1+nk+2 can be obtained due to nk mod nk+1=nk+2(0≤k≤t-1). So nk≥Ft-k can be concluded by mathematical induction. Furthermore, we can obtain m=n0≥Ft and n=n1≥Ft-1. That is to say, n must be not less than Ft-1 if our algorithm performs mod operation for t times and vice versa. We have Ft-1≥(1.618)t/5 according to the feature of Fibonacci sequence; namely, n≥(1.618)t/5 and t≤log1.618(5n), so the complexity of the algorithm is O(log⁡⁡n) in the worst case.


## 3.1. The Principles for Fraction Reduction

Assume that we have integersm, n (0<n<m) and let n0=m, n1=n, the sequences {ai}, {ni}, and {ki} can be constructed as
(3)ai=nini-1=1ki+(ni+1/ni),0≤ni+1<ni,i≥1,
where, for i≥1,
(4)ki=ni-1div⁡ni,ni+1=ni-1mod⁡ni.
For {n0,n1,…,nρ}, we have the following.Theorem 1.
Integer sequence{n0,n1,…,nρ} is monotone decreasing, and there is an integer v>0, such that nv=0.Proof.
(i) Obviously,{n0,n1,…,nρ} is monotone decreasing according to the procedure of the construction.
(ii) Assume thatnt is the minimum in {n0,n1,…,nρ} and nt>0. From the construction, we have
(5)nt+1=nt-1mod⁡nt.
It is easy to see that0≤nt+1<nt. According to the assumption, we obtain nt+1=0 and let v=t+1, namely, nv=0.From (3), we have
(6)at=ntnt-1=1kt+(nt+1/nt)=1kt,ai=1ki+ai+1,0≤i<t-1.The sequence{fi} can be constructed as follows:
(7)ft+1=1,ft=kt,ft-1=kt-1×ft+1.Generally,(8)fi=ki×fi+1+fi+2,1≤i<t-2.So,(9)at=1ft,at-1=1kt-1+at=1kt-1+(1/ft)=ftkt-1×ft+1=ftft-1,at-2=1kt-2+at-1=1kt-2+(ft/ft-1)=ft-1kt-2×ft-1+ft=ft-1ft-2.Generally, for0<i<t,
(10)ai=1ki+ai+1=1ki+(fi+2/fi+1)=fi+1ki×fi+1+fi+2=fi+1fi.Specifically,(11)a1=1k1+a2=f2k1×f2+f3=f2f1.Theorem 2.
f
1 and f2 are coprimes, and f2/f1 is the simplest proper fraction of n/m.Proof.
letξ be the common factor of f1 and f2. According to the construction of {fi}, we can obtain f1=k1×f2+f3, so ξ is also the factor of f3. Similarly, ξ is the common factor of ft-1 and ft. It means that there are ξ1 and ξ2, such that ft-1=ξ×ξ1 and ft=ξ×ξ2. According to the definition of ft-1, we have
(12)ft-1=ξ×ξ1=kt-1×(ξ×ξ2)+1.
That is,
(13)ξ×(ξ1-kt-1×ξ2)=1.
Namely, ξ is the factor of 1. Hence, ξ=1. So f1 and f2 are coprimes.
According to the construction of{ai} and (11), we have f2/f1=a1=n/m, so f2/f1 is the simplest proper fraction of n/m.The proofs of the above theories show that the proposed method is feasible for fraction reduction; namely, the simplest proper fraction can be obtained by this method for any fraction.


## 3.2. The Algorithm for Fraction Reduction

Assume that we want to reduce the fractionn/m (0<n<m); from the discussion in Section 3.1, the procedure for fraction reduction can be described as follows:(i)
inputn, m(0<n≤m);(ii)
compute{ni}, {ki}, i=2,3,…u, and n1=n, n0=m;(iii)
compute{fi}, i=t,t-1,…,1;(iv)
outputf1,f2.We can present an algorithm for fraction reduction in Algorithm1.Algorithm 1:Fraction reduction.
Input: n, m(m≥n>0);
Output:  f1,f2 (f2/f1 is the simplest proper fraction of n/m);
Procedure:
//calculate{ni}, {ki}
i←1;
n1←n, n0←m;
repeat
ki←ni-1div⁡ni;
ni+1←ni-1mod⁡ni;
i←i+1;
untilni+1=0;
//calculate{fi};
i←i-1;
fi+1←1;
fi←ki;
whilei>1  {
fi-1←ki-1*fi+fi+1;
i←i-1;
}
End.In this algorithm, the complexity of the algorithm isO(1) when m is a multiple of the n. Generally, for sequence {ni}, we know nt+1=0 if the algorithm performs mod operation for t times. Comparing sequence {ni} with Fibonacci sequence {Fi}, we have F0=1≤nt and F1=1≤nt-1. And nk≥nk+1+nk+2 can be obtained due to nk mod nk+1=nk+2(0≤k≤t-1). So nk≥Ft-k can be concluded by mathematical induction. Furthermore, we can obtain m=n0≥Ft and n=n1≥Ft-1. That is to say, n must be not less than Ft-1 if our algorithm performs mod operation for t times and vice versa. We have Ft-1≥(1.618)t/5 according to the feature of Fibonacci sequence; namely, n≥(1.618)t/5 and t≤log1.618(5n), so the complexity of the algorithm is O(log⁡⁡n) in the worst case.


## 4. Fraction Reduction in P Systems

In this section, a kind of P systems is designed for fraction reduction based on the algorithm proposed in Section3.2.


### 4.1. The P Systems for Fraction Reduction

The P systems for fraction reduction can be defined as the form of (1) given in Section 2.1, where:(i)
O is the (finite and nonempty) alphabet of objects which occur in the rules in the designed P system;(ii)
μ is the structure of the system and it can be decided by the rules presented subsequently;(iii)
io=1, and it means that the final result can be found in membrane 1 when the whole system halts.Figure1 describes the initial configuration of this P system: membrane 1 is responsible for keeping the final results and dissolving the other objects coming from membrane M1, while fraction reduction is processed in membrane M1. Except the two membranes, other membranes will be dynamically created during the reduction, and the rules in the new membranes are the same as the ones in membrane M1. In Figure 1, objects a and b are used to label the denominator and numerator, respectively; m and n, which are the cardinalities of a and b, represent the absolute value of the denominator and numerator, respectively; object c is used to trigger the rules in membrane M1.Figure 1
The initial configuration of P system for fraction reduction.The algorithm proposed in Section3.2 can be implemented by the P system as shown in Figure 2. In Figure 2, membrane M1 and the created membranes are responsible for computing {ni}, {ki}, and {fi}. These membranes are nested one by one: the new membrane M2 is created in membrane M1, and another new membrane M3 is created in membrane M2. Finally, membrane Mt is created in membrane Mt-1 (t is decided in Section 3.2).Schematic diagrams for the algorithm in Section3.2 being implemented by the P systems.
(a)
Calculating{ni} and {ki}
(b)
Calculating{fi}As shown in Figure2(a), the procedure of calculating {ni} and {ki} is as follows (the cardinalities of the objects are the items in {ni} and {ki}).(i)
In membraneM1, multiset an0 is consumed with new multisets an2 and kk1 produced by applying several rules. Furthermore, an2 and bn1 are sent into membrane M2, and kk1 is kept in M1.(ii)
Whenan2 and bn1 are sent into M2, they are converted to bn2 and an1, respectively. In membrane M2, an1 is consumed with new multisets an3 and kk2 produced. Furthermore, an3 and bn2 are sent into membrane M3, and kk2 is kept in M2.(iii)
Generally, in membraneMi(2≤i≤t-1), multisets ani and bni-1 coming from Mi-1 are transformed to bni and ani-1, respectively. And then ani-1 is consumed with the new multisets ani+1 and kki produced. Furthermore, ani+1 and bni are sent into membrane Mi+1, and kki is kept in Mi.(iv)
Finally,ant and bnt-1 leave membrane Mt-1 and they are transferred to bnt and ant-1, respectively, after arriving in membrane Mt. In membrane Mt, ant-1 is consumed with the kkt produced.As shown in Figure2(b), the procedure of calculating {fi} is as follows (the cardinalities of the objects are the items in {fi}).(i)
In membraneMt, multiset fft+1(ft+1=1) is produced and kkt (kkt is kept in membrane Mt previously) is transformed to qft (here, ft=kt). Then, fft+1 and qft are sent into membrane Mt-1.(ii)
Whenfft+1 and qft are sent into Mt-1, they are converted to qft+1 and fft, respectively. In membrane Mt-1, qft+1 and kkt-1 (kkt-1 is kept in membrane Mt-1 previously) are consumed with multisets qft-1 produced. Then, qft-1 and fft are sent into membrane Mt-2.(iii)
Generally, membraneMi+1 sends qfi+1 and ffi+2 into membrane Mi. qfi+1 and ffi+2 are transformed to ffi+1 and qfi+2 after arriving in membrane Mi. Then qfi+2 and kki (kki is kept in membrane Mi previously) are consumed with new multisets qfi produced.(iv)
When membraneM1 sends qf1 and ff2 into membrane 1, the cardinalities of objects f and q compose the result of the reduction, namely, f2/f1.For convenience, we have some conventions in the rest of the paper as follows.(i)
The rules should have priority, and they are described as the form (U→V, φ), where U→V is rewritten rule, and φ indicates the priority. The smaller value φ is set, higher priority the corresponding rule will have. When φ=1, the corresponding rule will have the highest priority. For example, there are two rules in membrane M1:r1: (ab→x, 1) and r2: (ay→ad, 2), and the priority of r1 is higher than r2, so the r1 will be applied firstly when both of them can be applied.(ii)
The created membranes namedM2,M3,…, and Mt and the rules in all of them are the same as the ones in membrane M1.(iii)
The objects appearing in the rest of the paper have the same meaning, so they will not be explained any more once they are introduced previously.


### 4.2. The Rules for Fraction Reduction

In this subsection the rules in the P systems for fraction reduction will be discussed in detail. There are two kinds of rules: one is in membrane 1 and the other is in membranesM1, M2, M3, …, and Mt.According to Section3, we know that the fraction reduction mainly includes calculating {ni}, {ki}, and {fi}. So membrane M1 and the created membranes M2, M3, …, and Mt should carry out the computations including division (for calculating {ni} and {ki}), multiplication and addition (for calculating {fi}).


#### 4.2.1. The Rules in MembraneM1

(i) Calculating
{
n
i
}
and
{
k
i
}
. Firstly multiset ambnc is put in membrane M1. In this membrane and the created membranes, object c evolves to y for controlling the division which is used to calculate {ni}, {ki}, and objects a and b label the denominator and numerator: in membrane M1, objects a and b label n0 and n1, respectively; in membrane M2, objects a and b label n1 and n2, respectively; in membrane M3, objects a and b label n2 and n3, respectively; …; in membrane Mt, objects a and b label nt-1 and nt, respectively.The rules for calculating{ni} and {ki} should include
(14)r1:(ab⟶x,1),r2:(c⟶y,1),r3:(ay⟶ad,2),r4:(x⟶b|d,3),r5:(d⟶kc,4),r6:(by⟶beg,2),r7:(e⟶[i]i|b,3),r8:(g⟶h,3),r9:(x⟶(ab,in)|h,4),r10:(b⟶(a,in)|h,4),r11:(h⟶(c,in),5),r12:(y⟶kze,3),r13:(x⟶λ|z,3),r14:(z⟶λ,4).Ifm>n, r1, r2, r3, r4, and r5 should be applied in the order of {r1,r2}→r3→{r4,r5} (for convenience, the rules rj1,rj2,…, and rjk will be represented as {rj1,rj2,…,rjk}, if they can be executed simultaneously). a and b are consumed by r1 with x produced; it means that the values of the numerator and denominator are subtracted by n simultaneously and (m-n) copies of object a will remain. Object y, which is produced by r2, evolves to d with the help of a by applying r3. Once d occurs, x evolves to b by applying r4 and it means that the numerator is restored for the next division. d evolves to kc by applying r5. This procedure may be repeated for several times. Finally, the cardinality of object k represents the quotient of the current division.Ifm<n,  r1,  r2,  r6,  r7,  r8,  r9,  r10, and r11 should be applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}. r1 and r2 are applied as described previously, and (n-m) copies of object b will remain. Object y, which is produced by r2, evolves to eg with the help of b by applying r6. By applying r7, e triggers to a new membrane to be created in the current membrane in the presence of object b and the new membrane will be used to calculate new items in {ni} and {ki}. In the presence of object h which is produced by r8, r9, and r10 will be applied: by r9, x evolves to ab (they will be sent into the new membrane), and it means that the numerator and denominator consumed by r1 will be restored in the created membrane; by r10, b evolves to a (a will be sent into the new membrane). The applications of r9 and r10 mean that the numerator becomes the new denominator and the denominator becomes the new numerator in the new membrane for the next division since the division rules will not be triggered in the case of m<n (there is multiset anbm in the new membrane). Object c will be produced and sent into the new membrane by applying r11.Ifm=n, r1, r2, r12, r13, and r14 should be applied in the order of {r1,r2}→r12→r13→r14. y evolves to kze by applying r12. In the presence of z, x will be dissolved by applying r13. Then z will be dissolved by applying r14. When e occurs in the innermost membrane, it means that the calculations of {ni} and {ki} will be ended.(ii) Calculating
{
f
i
}. The calculations of {ni} and {ki} will be terminated when object s appears and b does not appear in the innermost membrane. At this moment, the operations of multiplication and addition should be triggered to calculate {fi}.Concerning (10) in Section 3, we know that in membrane Mi in Figure 2(b), the copies of objects q and f will be produced at several steps. So we can design the rules to realize that multisets ffi-1 and qfi can be produced in membrane Mi-1 while multisets ffi and qfi+1 are produced in membrane Mi. Based on this consideration, we design the rules for calculating {fi} and they can be applied in several membranes simultaneously. For example, in membrane Mi in Figure 2(b), several copies of objects q and f are sent into membrane Mi-1 once they are produced and they will trigger the rules in membrane Mi-1. It means that the rules in membranes Mi and Mi-1 will be applied together at the subsequent steps. Maximal parallelism is implemented in the P systems for fraction reduction.The rules for the operations of multiplication and addition can be designed as follows:(15)r15:(e⟶pr,4),r16:(r⟶(f,out),2),r17:(k⟶(q,out)|p,1),r18:(p⟶(ojw,out)δ,2),r19:(w⟶(ojw,out),3),r20:(f⟶(q,out),3),r21:(k⟶k(q,out)|q,3),r22:(o⟶v|q,3),r23:(qj⟶j(f,out),3),r24:(v⟶o,4),r25:(k⟶λ|o,4),r26:(j⟶λ|o,4),r27:(o⟶δ,5).Ruler15 is only applied in the innermost membrane Mt and is responsible for e evolving to pr. Object r evolves to f by applying r16, and it means that 1 is assigned to ft+1 in membrane Mt as shown in Figure 2(b). f and q represent the numerator and denominator, respectively. Object k evolves to q and q is sent into the outer membrane in the presence of p by applying r17 (it is only applied in membrane Mt); it means that kt is assigned to ft in membrane Mt as shown in Figure 2(b). Rule r18 is only applied in membrane Mt and is responsible for sending out multiset ojw to the outer membrane Mt-1. Simultaneously, membrane Mt is dissolved because of the occurrence of the special symbol δ when r18 is applied.Except for the rulesr15~r18, the rest of the rules are available in Mt-1, Mt-2, …, and M1. By applying r19, object w evolves to ojw and ojw is sent into the outer membrane for triggering rules r19, r22, and r23 in the outer membrane. Object f coming from the inner membrane evolves to q and q is sent into the outer membrane by applying r20. Rules r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane. Rule r23 is applied to generate objects j and f (f is sent into the outer membrane). Rules r17, r20, r21, and r23 are responsible for calculating {fi} as shown in Figure 2(b). Object v evolves to o by applying r24 for triggering rules r25~r27. Rules r25 and r26 are applied to consume objects k and j completely in the presence of object o. Rule r27 is applied to dissolve the current membranes.


#### 4.2.2. The Rule in Membrane 1

There is only one rule in membrane 1 and it is responsible for keeping the final results and dissolving the objects coming from membraneM1. The rule can be designed as
(16)r28:(ojw⟶λ,1),
where objects o, j, and w sent from membrane M1 are dissolved.Owing to maximal parallelism, the complexity of the P systems for fraction reduction must be not more thanO(log⁡⁡n).


### 4.3. The Instance for Fraction Reduction

In this subsection, we will give an instance to show how to implement the fraction reduction in the P system designed previously. For example, 6/10 can be reduced by the P system as shown in Figure3.Figure 3
Schematic diagram for reducing 6/10 by the P system.The rules in this P system can be applied as follows.


#### 4.3.1. Initial Configuration

Firstly multiseta10b6c is put in membrane M1, as Figure 4(a) shows: the cardinality of object a is 10, and it is the denominator of the fraction; the cardinality of object b is 6 and it is the numerator.The procedure of reducing 6/10 in the designed P system.
(a)
Initial configuration
(b)
Moves new denominator and numerator to membraneM2
(c)
Moves new denominator and numerator to membraneM3
(d)
Division is performed in membraneM3
(e)
Ruler15 is applied in membrane M3
(f)
MembraneM3 is dissolved
(g)
Rules are applied in membranesM2 and M1
(h)
Rules are applied in membranes 1,M1, and M2
(i)
MembraneM2 is dissolved
(j)
System halts and the final result can be obtained


#### 4.3.2. Calculating{ni} and {ki}

(i)
In Figure4(a), rule r1 is applied 6 times to generate multiset x6 until b6 is consumed completely, and rule r2 is applied to generate y at the same time. Then only rule r3 can be applied to generate multiset ad. Rule r4 is applied to restore x6 to b6 in the presence of object d. At the same time, r5 is applied to generate multiset ck and there is multiset a4b6ck in membrane M1. In this case, due to the fact that the cardinality of a is less than the one of b, the available rules are applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}:r1 is applied 4 times to consume a4 completely; r6 is applied to generate multiset beg; by applying r7, a new membrane is created with the label M2; by applying r9, r10, and r11, x4 and b2 are sent into the new created membrane as the new numerator and denominator with object h also sent into the new membrane (see Figure 4(b)).
(ii)
At this moment, there is multiseta6b4c in membrane M2 (see Figure 4(b)). Hence, the available rules are applied in the order of {r1,r2}→r3→{r4,r5} to generate multiset a2b4ck. Owing to the fact that the cardinality of a is less than the one of b, the available rules are applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}: by applying r7, a new membrane is created with the label M3; by applying r9, r10, and r11, x2 and b2 are sent into the new created membrane as the new numerator and denominator with object h also sent into the new membrane (see Figure 4(c)).
(iii)
There is multiseta4b2c in membrane M3; the available rules are applied in the order of {r1,r2}→r3→{r4,r5} to generate multiset a2b2ck. Due to the fact that the cardinality of a equals the one of b, the available rules are applied in the order of {r1,r2}→r12→r13→r14:r12 is applied to generate multiset kze; r13 is applied 2 times to consume x2 completely; then z will be dissolved by applying r14 (see Figure 4(d)).


#### 4.3.3. Calculating{fi}

(i)
There is multisetk2e in membrane M3, and r15 is applied to generate multiset pr (see Figure 4(e)).
(ii)
There is multisetk2pr in membrane M3 now. At this moment, r16 is applied to generate f and f is sent into the outer membrane. Then r17 is applied 2 times to generate q2 and q2 is sent into the outer membrane in the presence of object p. Rule r18 is applied to generate multiset ojwδ and ojw is sent into the outer membrane. Simultaneously, membrane M3 is dissolved (see Figure 4(f)).
(iii)
There is multisetq2fkojw in membrane M2. The following rules can be applied in a step: r19 and r20 are applied to generate objects q, o, j, and w (all of them are sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane) (see Figure 4(g)).
(iv)
There are multisetsq2fkojw and qkjv in membranes M1 and M2, respectively. In membrane M1, the following rules can be applied in a step: r19 and r20 are applied to generate objects q, o, j, and w (all of them are sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane). Simultaneously in membrane M2, the available rules can be applied: r21 is applied to generate multiset kq in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate multiset fj and f is sent into the outer membrane, and r24 is applied to generate object o at the same time (see Figure 4(h)).
(v)
There are multisetsq2fojw, q2fkjv, and kjo in membranes 1, M1, and M2, respectively. In membrane 1, rule r28 is applied to consume multiset ojw completely. In membrane M1, the following rules can be applied in a step: r20 is applied to generate object q (q is sent into the outer membrane); r21 is applied to generate objects q and k in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane); r24 is applied to generate object o. In membrane M2, rules r25 and r26 are applied to consume objects k and j completely; then membrane M2 is dissolved after applying r27 (see Figure 4(i)). The aforementioned rules in membranes 1, M1, and M2 are applied simultaneously.
(vi)
There are multisetsq4f2 and qkjo in membranes 1 and M1, respectively. In membrane M1, the following rules can be applied in a step: r20 is applied to generate object q (q is sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane). Then there is multiset kjv in membrane M1, so the following rules can be applied: r24 is applied to generate object o; r25 and r26 are applied to consume objects k and j completely; membrane M1 is dissolved after applying r27 (see Figure 4(j)).
(vii)
There is multisetq5f3 in membrane 1 (see Figure 4(j)). At this time, no rules can be applied, so the whole system halts. The cardinalities of q and f represent the values of the denominator and numerator, respectively, so the final result of reducing 6/10 is 3/5.


## 4.1. The P Systems for Fraction Reduction

The P systems for fraction reduction can be defined as the form of (1) given in Section 2.1, where:(i)
O is the (finite and nonempty) alphabet of objects which occur in the rules in the designed P system;(ii)
μ is the structure of the system and it can be decided by the rules presented subsequently;(iii)
io=1, and it means that the final result can be found in membrane 1 when the whole system halts.Figure1 describes the initial configuration of this P system: membrane 1 is responsible for keeping the final results and dissolving the other objects coming from membrane M1, while fraction reduction is processed in membrane M1. Except the two membranes, other membranes will be dynamically created during the reduction, and the rules in the new membranes are the same as the ones in membrane M1. In Figure 1, objects a and b are used to label the denominator and numerator, respectively; m and n, which are the cardinalities of a and b, represent the absolute value of the denominator and numerator, respectively; object c is used to trigger the rules in membrane M1.Figure 1
The initial configuration of P system for fraction reduction.The algorithm proposed in Section3.2 can be implemented by the P system as shown in Figure 2. In Figure 2, membrane M1 and the created membranes are responsible for computing {ni}, {ki}, and {fi}. These membranes are nested one by one: the new membrane M2 is created in membrane M1, and another new membrane M3 is created in membrane M2. Finally, membrane Mt is created in membrane Mt-1 (t is decided in Section 3.2).Schematic diagrams for the algorithm in Section3.2 being implemented by the P systems.
(a)
Calculating{ni} and {ki}
(b)
Calculating{fi}As shown in Figure2(a), the procedure of calculating {ni} and {ki} is as follows (the cardinalities of the objects are the items in {ni} and {ki}).(i)
In membraneM1, multiset an0 is consumed with new multisets an2 and kk1 produced by applying several rules. Furthermore, an2 and bn1 are sent into membrane M2, and kk1 is kept in M1.(ii)
Whenan2 and bn1 are sent into M2, they are converted to bn2 and an1, respectively. In membrane M2, an1 is consumed with new multisets an3 and kk2 produced. Furthermore, an3 and bn2 are sent into membrane M3, and kk2 is kept in M2.(iii)
Generally, in membraneMi(2≤i≤t-1), multisets ani and bni-1 coming from Mi-1 are transformed to bni and ani-1, respectively. And then ani-1 is consumed with the new multisets ani+1 and kki produced. Furthermore, ani+1 and bni are sent into membrane Mi+1, and kki is kept in Mi.(iv)
Finally,ant and bnt-1 leave membrane Mt-1 and they are transferred to bnt and ant-1, respectively, after arriving in membrane Mt. In membrane Mt, ant-1 is consumed with the kkt produced.As shown in Figure2(b), the procedure of calculating {fi} is as follows (the cardinalities of the objects are the items in {fi}).(i)
In membraneMt, multiset fft+1(ft+1=1) is produced and kkt (kkt is kept in membrane Mt previously) is transformed to qft (here, ft=kt). Then, fft+1 and qft are sent into membrane Mt-1.(ii)
Whenfft+1 and qft are sent into Mt-1, they are converted to qft+1 and fft, respectively. In membrane Mt-1, qft+1 and kkt-1 (kkt-1 is kept in membrane Mt-1 previously) are consumed with multisets qft-1 produced. Then, qft-1 and fft are sent into membrane Mt-2.(iii)
Generally, membraneMi+1 sends qfi+1 and ffi+2 into membrane Mi. qfi+1 and ffi+2 are transformed to ffi+1 and qfi+2 after arriving in membrane Mi. Then qfi+2 and kki (kki is kept in membrane Mi previously) are consumed with new multisets qfi produced.(iv)
When membraneM1 sends qf1 and ff2 into membrane 1, the cardinalities of objects f and q compose the result of the reduction, namely, f2/f1.For convenience, we have some conventions in the rest of the paper as follows.(i)
The rules should have priority, and they are described as the form (U→V, φ), where U→V is rewritten rule, and φ indicates the priority. The smaller value φ is set, higher priority the corresponding rule will have. When φ=1, the corresponding rule will have the highest priority. For example, there are two rules in membrane M1:r1: (ab→x, 1) and r2: (ay→ad, 2), and the priority of r1 is higher than r2, so the r1 will be applied firstly when both of them can be applied.(ii)
The created membranes namedM2,M3,…, and Mt and the rules in all of them are the same as the ones in membrane M1.(iii)
The objects appearing in the rest of the paper have the same meaning, so they will not be explained any more once they are introduced previously.


## 4.2. The Rules for Fraction Reduction

In this subsection the rules in the P systems for fraction reduction will be discussed in detail. There are two kinds of rules: one is in membrane 1 and the other is in membranesM1, M2, M3, …, and Mt.According to Section3, we know that the fraction reduction mainly includes calculating {ni}, {ki}, and {fi}. So membrane M1 and the created membranes M2, M3, …, and Mt should carry out the computations including division (for calculating {ni} and {ki}), multiplication and addition (for calculating {fi}).


### 4.2.1. The Rules in MembraneM1

(i) Calculating
{
n
i
}
and
{
k
i
}
. Firstly multiset ambnc is put in membrane M1. In this membrane and the created membranes, object c evolves to y for controlling the division which is used to calculate {ni}, {ki}, and objects a and b label the denominator and numerator: in membrane M1, objects a and b label n0 and n1, respectively; in membrane M2, objects a and b label n1 and n2, respectively; in membrane M3, objects a and b label n2 and n3, respectively; …; in membrane Mt, objects a and b label nt-1 and nt, respectively.The rules for calculating{ni} and {ki} should include
(14)r1:(ab⟶x,1),r2:(c⟶y,1),r3:(ay⟶ad,2),r4:(x⟶b|d,3),r5:(d⟶kc,4),r6:(by⟶beg,2),r7:(e⟶[i]i|b,3),r8:(g⟶h,3),r9:(x⟶(ab,in)|h,4),r10:(b⟶(a,in)|h,4),r11:(h⟶(c,in),5),r12:(y⟶kze,3),r13:(x⟶λ|z,3),r14:(z⟶λ,4).Ifm>n, r1, r2, r3, r4, and r5 should be applied in the order of {r1,r2}→r3→{r4,r5} (for convenience, the rules rj1,rj2,…, and rjk will be represented as {rj1,rj2,…,rjk}, if they can be executed simultaneously). a and b are consumed by r1 with x produced; it means that the values of the numerator and denominator are subtracted by n simultaneously and (m-n) copies of object a will remain. Object y, which is produced by r2, evolves to d with the help of a by applying r3. Once d occurs, x evolves to b by applying r4 and it means that the numerator is restored for the next division. d evolves to kc by applying r5. This procedure may be repeated for several times. Finally, the cardinality of object k represents the quotient of the current division.Ifm<n,  r1,  r2,  r6,  r7,  r8,  r9,  r10, and r11 should be applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}. r1 and r2 are applied as described previously, and (n-m) copies of object b will remain. Object y, which is produced by r2, evolves to eg with the help of b by applying r6. By applying r7, e triggers to a new membrane to be created in the current membrane in the presence of object b and the new membrane will be used to calculate new items in {ni} and {ki}. In the presence of object h which is produced by r8, r9, and r10 will be applied: by r9, x evolves to ab (they will be sent into the new membrane), and it means that the numerator and denominator consumed by r1 will be restored in the created membrane; by r10, b evolves to a (a will be sent into the new membrane). The applications of r9 and r10 mean that the numerator becomes the new denominator and the denominator becomes the new numerator in the new membrane for the next division since the division rules will not be triggered in the case of m<n (there is multiset anbm in the new membrane). Object c will be produced and sent into the new membrane by applying r11.Ifm=n, r1, r2, r12, r13, and r14 should be applied in the order of {r1,r2}→r12→r13→r14. y evolves to kze by applying r12. In the presence of z, x will be dissolved by applying r13. Then z will be dissolved by applying r14. When e occurs in the innermost membrane, it means that the calculations of {ni} and {ki} will be ended.(ii) Calculating
{
f
i
}. The calculations of {ni} and {ki} will be terminated when object s appears and b does not appear in the innermost membrane. At this moment, the operations of multiplication and addition should be triggered to calculate {fi}.Concerning (10) in Section 3, we know that in membrane Mi in Figure 2(b), the copies of objects q and f will be produced at several steps. So we can design the rules to realize that multisets ffi-1 and qfi can be produced in membrane Mi-1 while multisets ffi and qfi+1 are produced in membrane Mi. Based on this consideration, we design the rules for calculating {fi} and they can be applied in several membranes simultaneously. For example, in membrane Mi in Figure 2(b), several copies of objects q and f are sent into membrane Mi-1 once they are produced and they will trigger the rules in membrane Mi-1. It means that the rules in membranes Mi and Mi-1 will be applied together at the subsequent steps. Maximal parallelism is implemented in the P systems for fraction reduction.The rules for the operations of multiplication and addition can be designed as follows:(15)r15:(e⟶pr,4),r16:(r⟶(f,out),2),r17:(k⟶(q,out)|p,1),r18:(p⟶(ojw,out)δ,2),r19:(w⟶(ojw,out),3),r20:(f⟶(q,out),3),r21:(k⟶k(q,out)|q,3),r22:(o⟶v|q,3),r23:(qj⟶j(f,out),3),r24:(v⟶o,4),r25:(k⟶λ|o,4),r26:(j⟶λ|o,4),r27:(o⟶δ,5).Ruler15 is only applied in the innermost membrane Mt and is responsible for e evolving to pr. Object r evolves to f by applying r16, and it means that 1 is assigned to ft+1 in membrane Mt as shown in Figure 2(b). f and q represent the numerator and denominator, respectively. Object k evolves to q and q is sent into the outer membrane in the presence of p by applying r17 (it is only applied in membrane Mt); it means that kt is assigned to ft in membrane Mt as shown in Figure 2(b). Rule r18 is only applied in membrane Mt and is responsible for sending out multiset ojw to the outer membrane Mt-1. Simultaneously, membrane Mt is dissolved because of the occurrence of the special symbol δ when r18 is applied.Except for the rulesr15~r18, the rest of the rules are available in Mt-1, Mt-2, …, and M1. By applying r19, object w evolves to ojw and ojw is sent into the outer membrane for triggering rules r19, r22, and r23 in the outer membrane. Object f coming from the inner membrane evolves to q and q is sent into the outer membrane by applying r20. Rules r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane. Rule r23 is applied to generate objects j and f (f is sent into the outer membrane). Rules r17, r20, r21, and r23 are responsible for calculating {fi} as shown in Figure 2(b). Object v evolves to o by applying r24 for triggering rules r25~r27. Rules r25 and r26 are applied to consume objects k and j completely in the presence of object o. Rule r27 is applied to dissolve the current membranes.


### 4.2.2. The Rule in Membrane 1

There is only one rule in membrane 1 and it is responsible for keeping the final results and dissolving the objects coming from membraneM1. The rule can be designed as
(16)r28:(ojw⟶λ,1),
where objects o, j, and w sent from membrane M1 are dissolved.Owing to maximal parallelism, the complexity of the P systems for fraction reduction must be not more thanO(log⁡⁡n).


## 4.2.1. The Rules in MembraneM1

(i) Calculating
{
n
i
}
and
{
k
i
}
. Firstly multiset ambnc is put in membrane M1. In this membrane and the created membranes, object c evolves to y for controlling the division which is used to calculate {ni}, {ki}, and objects a and b label the denominator and numerator: in membrane M1, objects a and b label n0 and n1, respectively; in membrane M2, objects a and b label n1 and n2, respectively; in membrane M3, objects a and b label n2 and n3, respectively; …; in membrane Mt, objects a and b label nt-1 and nt, respectively.The rules for calculating{ni} and {ki} should include
(14)r1:(ab⟶x,1),r2:(c⟶y,1),r3:(ay⟶ad,2),r4:(x⟶b|d,3),r5:(d⟶kc,4),r6:(by⟶beg,2),r7:(e⟶[i]i|b,3),r8:(g⟶h,3),r9:(x⟶(ab,in)|h,4),r10:(b⟶(a,in)|h,4),r11:(h⟶(c,in),5),r12:(y⟶kze,3),r13:(x⟶λ|z,3),r14:(z⟶λ,4).Ifm>n, r1, r2, r3, r4, and r5 should be applied in the order of {r1,r2}→r3→{r4,r5} (for convenience, the rules rj1,rj2,…, and rjk will be represented as {rj1,rj2,…,rjk}, if they can be executed simultaneously). a and b are consumed by r1 with x produced; it means that the values of the numerator and denominator are subtracted by n simultaneously and (m-n) copies of object a will remain. Object y, which is produced by r2, evolves to d with the help of a by applying r3. Once d occurs, x evolves to b by applying r4 and it means that the numerator is restored for the next division. d evolves to kc by applying r5. This procedure may be repeated for several times. Finally, the cardinality of object k represents the quotient of the current division.Ifm<n,  r1,  r2,  r6,  r7,  r8,  r9,  r10, and r11 should be applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}. r1 and r2 are applied as described previously, and (n-m) copies of object b will remain. Object y, which is produced by r2, evolves to eg with the help of b by applying r6. By applying r7, e triggers to a new membrane to be created in the current membrane in the presence of object b and the new membrane will be used to calculate new items in {ni} and {ki}. In the presence of object h which is produced by r8, r9, and r10 will be applied: by r9, x evolves to ab (they will be sent into the new membrane), and it means that the numerator and denominator consumed by r1 will be restored in the created membrane; by r10, b evolves to a (a will be sent into the new membrane). The applications of r9 and r10 mean that the numerator becomes the new denominator and the denominator becomes the new numerator in the new membrane for the next division since the division rules will not be triggered in the case of m<n (there is multiset anbm in the new membrane). Object c will be produced and sent into the new membrane by applying r11.Ifm=n, r1, r2, r12, r13, and r14 should be applied in the order of {r1,r2}→r12→r13→r14. y evolves to kze by applying r12. In the presence of z, x will be dissolved by applying r13. Then z will be dissolved by applying r14. When e occurs in the innermost membrane, it means that the calculations of {ni} and {ki} will be ended.(ii) Calculating
{
f
i
}. The calculations of {ni} and {ki} will be terminated when object s appears and b does not appear in the innermost membrane. At this moment, the operations of multiplication and addition should be triggered to calculate {fi}.Concerning (10) in Section 3, we know that in membrane Mi in Figure 2(b), the copies of objects q and f will be produced at several steps. So we can design the rules to realize that multisets ffi-1 and qfi can be produced in membrane Mi-1 while multisets ffi and qfi+1 are produced in membrane Mi. Based on this consideration, we design the rules for calculating {fi} and they can be applied in several membranes simultaneously. For example, in membrane Mi in Figure 2(b), several copies of objects q and f are sent into membrane Mi-1 once they are produced and they will trigger the rules in membrane Mi-1. It means that the rules in membranes Mi and Mi-1 will be applied together at the subsequent steps. Maximal parallelism is implemented in the P systems for fraction reduction.The rules for the operations of multiplication and addition can be designed as follows:(15)r15:(e⟶pr,4),r16:(r⟶(f,out),2),r17:(k⟶(q,out)|p,1),r18:(p⟶(ojw,out)δ,2),r19:(w⟶(ojw,out),3),r20:(f⟶(q,out),3),r21:(k⟶k(q,out)|q,3),r22:(o⟶v|q,3),r23:(qj⟶j(f,out),3),r24:(v⟶o,4),r25:(k⟶λ|o,4),r26:(j⟶λ|o,4),r27:(o⟶δ,5).Ruler15 is only applied in the innermost membrane Mt and is responsible for e evolving to pr. Object r evolves to f by applying r16, and it means that 1 is assigned to ft+1 in membrane Mt as shown in Figure 2(b). f and q represent the numerator and denominator, respectively. Object k evolves to q and q is sent into the outer membrane in the presence of p by applying r17 (it is only applied in membrane Mt); it means that kt is assigned to ft in membrane Mt as shown in Figure 2(b). Rule r18 is only applied in membrane Mt and is responsible for sending out multiset ojw to the outer membrane Mt-1. Simultaneously, membrane Mt is dissolved because of the occurrence of the special symbol δ when r18 is applied.Except for the rulesr15~r18, the rest of the rules are available in Mt-1, Mt-2, …, and M1. By applying r19, object w evolves to ojw and ojw is sent into the outer membrane for triggering rules r19, r22, and r23 in the outer membrane. Object f coming from the inner membrane evolves to q and q is sent into the outer membrane by applying r20. Rules r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane. Rule r23 is applied to generate objects j and f (f is sent into the outer membrane). Rules r17, r20, r21, and r23 are responsible for calculating {fi} as shown in Figure 2(b). Object v evolves to o by applying r24 for triggering rules r25~r27. Rules r25 and r26 are applied to consume objects k and j completely in the presence of object o. Rule r27 is applied to dissolve the current membranes.


## 4.2.2. The Rule in Membrane 1

There is only one rule in membrane 1 and it is responsible for keeping the final results and dissolving the objects coming from membraneM1. The rule can be designed as
(16)r28:(ojw⟶λ,1),
where objects o, j, and w sent from membrane M1 are dissolved.Owing to maximal parallelism, the complexity of the P systems for fraction reduction must be not more thanO(log⁡⁡n).


## 4.3. The Instance for Fraction Reduction

In this subsection, we will give an instance to show how to implement the fraction reduction in the P system designed previously. For example, 6/10 can be reduced by the P system as shown in Figure3.Figure 3
Schematic diagram for reducing 6/10 by the P system.The rules in this P system can be applied as follows.


### 4.3.1. Initial Configuration

Firstly multiseta10b6c is put in membrane M1, as Figure 4(a) shows: the cardinality of object a is 10, and it is the denominator of the fraction; the cardinality of object b is 6 and it is the numerator.The procedure of reducing 6/10 in the designed P system.
(a)
Initial configuration
(b)
Moves new denominator and numerator to membraneM2
(c)
Moves new denominator and numerator to membraneM3
(d)
Division is performed in membraneM3
(e)
Ruler15 is applied in membrane M3
(f)
MembraneM3 is dissolved
(g)
Rules are applied in membranesM2 and M1
(h)
Rules are applied in membranes 1,M1, and M2
(i)
MembraneM2 is dissolved
(j)
System halts and the final result can be obtained


### 4.3.2. Calculating{ni} and {ki}

(i)
In Figure4(a), rule r1 is applied 6 times to generate multiset x6 until b6 is consumed completely, and rule r2 is applied to generate y at the same time. Then only rule r3 can be applied to generate multiset ad. Rule r4 is applied to restore x6 to b6 in the presence of object d. At the same time, r5 is applied to generate multiset ck and there is multiset a4b6ck in membrane M1. In this case, due to the fact that the cardinality of a is less than the one of b, the available rules are applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}:r1 is applied 4 times to consume a4 completely; r6 is applied to generate multiset beg; by applying r7, a new membrane is created with the label M2; by applying r9, r10, and r11, x4 and b2 are sent into the new created membrane as the new numerator and denominator with object h also sent into the new membrane (see Figure 4(b)).
(ii)
At this moment, there is multiseta6b4c in membrane M2 (see Figure 4(b)). Hence, the available rules are applied in the order of {r1,r2}→r3→{r4,r5} to generate multiset a2b4ck. Owing to the fact that the cardinality of a is less than the one of b, the available rules are applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}: by applying r7, a new membrane is created with the label M3; by applying r9, r10, and r11, x2 and b2 are sent into the new created membrane as the new numerator and denominator with object h also sent into the new membrane (see Figure 4(c)).
(iii)
There is multiseta4b2c in membrane M3; the available rules are applied in the order of {r1,r2}→r3→{r4,r5} to generate multiset a2b2ck. Due to the fact that the cardinality of a equals the one of b, the available rules are applied in the order of {r1,r2}→r12→r13→r14:r12 is applied to generate multiset kze; r13 is applied 2 times to consume x2 completely; then z will be dissolved by applying r14 (see Figure 4(d)).


### 4.3.3. Calculating{fi}

(i)
There is multisetk2e in membrane M3, and r15 is applied to generate multiset pr (see Figure 4(e)).
(ii)
There is multisetk2pr in membrane M3 now. At this moment, r16 is applied to generate f and f is sent into the outer membrane. Then r17 is applied 2 times to generate q2 and q2 is sent into the outer membrane in the presence of object p. Rule r18 is applied to generate multiset ojwδ and ojw is sent into the outer membrane. Simultaneously, membrane M3 is dissolved (see Figure 4(f)).
(iii)
There is multisetq2fkojw in membrane M2. The following rules can be applied in a step: r19 and r20 are applied to generate objects q, o, j, and w (all of them are sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane) (see Figure 4(g)).
(iv)
There are multisetsq2fkojw and qkjv in membranes M1 and M2, respectively. In membrane M1, the following rules can be applied in a step: r19 and r20 are applied to generate objects q, o, j, and w (all of them are sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane). Simultaneously in membrane M2, the available rules can be applied: r21 is applied to generate multiset kq in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate multiset fj and f is sent into the outer membrane, and r24 is applied to generate object o at the same time (see Figure 4(h)).
(v)
There are multisetsq2fojw, q2fkjv, and kjo in membranes 1, M1, and M2, respectively. In membrane 1, rule r28 is applied to consume multiset ojw completely. In membrane M1, the following rules can be applied in a step: r20 is applied to generate object q (q is sent into the outer membrane); r21 is applied to generate objects q and k in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane); r24 is applied to generate object o. In membrane M2, rules r25 and r26 are applied to consume objects k and j completely; then membrane M2 is dissolved after applying r27 (see Figure 4(i)). The aforementioned rules in membranes 1, M1, and M2 are applied simultaneously.
(vi)
There are multisetsq4f2 and qkjo in membranes 1 and M1, respectively. In membrane M1, the following rules can be applied in a step: r20 is applied to generate object q (q is sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane). Then there is multiset kjv in membrane M1, so the following rules can be applied: r24 is applied to generate object o; r25 and r26 are applied to consume objects k and j completely; membrane M1 is dissolved after applying r27 (see Figure 4(j)).
(vii)
There is multisetq5f3 in membrane 1 (see Figure 4(j)). At this time, no rules can be applied, so the whole system halts. The cardinalities of q and f represent the values of the denominator and numerator, respectively, so the final result of reducing 6/10 is 3/5.


## 4.3.1. Initial Configuration

Firstly multiseta10b6c is put in membrane M1, as Figure 4(a) shows: the cardinality of object a is 10, and it is the denominator of the fraction; the cardinality of object b is 6 and it is the numerator.The procedure of reducing 6/10 in the designed P system.
(a)
Initial configuration
(b)
Moves new denominator and numerator to membraneM2
(c)
Moves new denominator and numerator to membraneM3
(d)
Division is performed in membraneM3
(e)
Ruler15 is applied in membrane M3
(f)
MembraneM3 is dissolved
(g)
Rules are applied in membranesM2 and M1
(h)
Rules are applied in membranes 1,M1, and M2
(i)
MembraneM2 is dissolved
(j)
System halts and the final result can be obtained


## 4.3.2. Calculating{ni} and {ki}

(i)
In Figure4(a), rule r1 is applied 6 times to generate multiset x6 until b6 is consumed completely, and rule r2 is applied to generate y at the same time. Then only rule r3 can be applied to generate multiset ad. Rule r4 is applied to restore x6 to b6 in the presence of object d. At the same time, r5 is applied to generate multiset ck and there is multiset a4b6ck in membrane M1. In this case, due to the fact that the cardinality of a is less than the one of b, the available rules are applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}:r1 is applied 4 times to consume a4 completely; r6 is applied to generate multiset beg; by applying r7, a new membrane is created with the label M2; by applying r9, r10, and r11, x4 and b2 are sent into the new created membrane as the new numerator and denominator with object h also sent into the new membrane (see Figure 4(b)).
(ii)
At this moment, there is multiseta6b4c in membrane M2 (see Figure 4(b)). Hence, the available rules are applied in the order of {r1,r2}→r3→{r4,r5} to generate multiset a2b4ck. Owing to the fact that the cardinality of a is less than the one of b, the available rules are applied in the order of {r1,r2}→r6→{r7,r8}→{r9,r10,r11}: by applying r7, a new membrane is created with the label M3; by applying r9, r10, and r11, x2 and b2 are sent into the new created membrane as the new numerator and denominator with object h also sent into the new membrane (see Figure 4(c)).
(iii)
There is multiseta4b2c in membrane M3; the available rules are applied in the order of {r1,r2}→r3→{r4,r5} to generate multiset a2b2ck. Due to the fact that the cardinality of a equals the one of b, the available rules are applied in the order of {r1,r2}→r12→r13→r14:r12 is applied to generate multiset kze; r13 is applied 2 times to consume x2 completely; then z will be dissolved by applying r14 (see Figure 4(d)).


## 4.3.3. Calculating{fi}

(i)
There is multisetk2e in membrane M3, and r15 is applied to generate multiset pr (see Figure 4(e)).
(ii)
There is multisetk2pr in membrane M3 now. At this moment, r16 is applied to generate f and f is sent into the outer membrane. Then r17 is applied 2 times to generate q2 and q2 is sent into the outer membrane in the presence of object p. Rule r18 is applied to generate multiset ojwδ and ojw is sent into the outer membrane. Simultaneously, membrane M3 is dissolved (see Figure 4(f)).
(iii)
There is multisetq2fkojw in membrane M2. The following rules can be applied in a step: r19 and r20 are applied to generate objects q, o, j, and w (all of them are sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane) (see Figure 4(g)).
(iv)
There are multisetsq2fkojw and qkjv in membranes M1 and M2, respectively. In membrane M1, the following rules can be applied in a step: r19 and r20 are applied to generate objects q, o, j, and w (all of them are sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane). Simultaneously in membrane M2, the available rules can be applied: r21 is applied to generate multiset kq in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate multiset fj and f is sent into the outer membrane, and r24 is applied to generate object o at the same time (see Figure 4(h)).
(v)
There are multisetsq2fojw, q2fkjv, and kjo in membranes 1, M1, and M2, respectively. In membrane 1, rule r28 is applied to consume multiset ojw completely. In membrane M1, the following rules can be applied in a step: r20 is applied to generate object q (q is sent into the outer membrane); r21 is applied to generate objects q and k in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane); r24 is applied to generate object o. In membrane M2, rules r25 and r26 are applied to consume objects k and j completely; then membrane M2 is dissolved after applying r27 (see Figure 4(i)). The aforementioned rules in membranes 1, M1, and M2 are applied simultaneously.
(vi)
There are multisetsq4f2 and qkjo in membranes 1 and M1, respectively. In membrane M1, the following rules can be applied in a step: r20 is applied to generate object q (q is sent into the outer membrane); r21 and r22 are applied to generate objects q, k, and v both in the presence of object q and the new generated object q is sent into the outer membrane; r23 is applied to generate objects j and f (f is sent into the outer membrane). Then there is multiset kjv in membrane M1, so the following rules can be applied: r24 is applied to generate object o; r25 and r26 are applied to consume objects k and j completely; membrane M1 is dissolved after applying r27 (see Figure 4(j)).
(vii)
There is multisetq5f3 in membrane 1 (see Figure 4(j)). At this time, no rules can be applied, so the whole system halts. The cardinalities of q and f represent the values of the denominator and numerator, respectively, so the final result of reducing 6/10 is 3/5.


## 5. Conclusions

Fraction (rational number) computing is foundational in most of the computing models and systems, and the computation results of the fractions often need to be reduced to lighten the load of the subsequent computations. This paper proposes and proves a new suitable reduction method and implements it in P systems. Furthermore, we give an instance to illustrate how to carry out the fraction reduction effectively in this system. For the fact that the rational number can be given by the form of fraction, whose numerator and denominator can be represented by multisets, respectively, our work will contribute to implementing the computation of the rational numbers in P systems. Further, we will research the signed fraction reduction in P systems and the fraction reduction in the case that the denominator or numerator is 0.



---

*Source: 858527-2014-03-16.xml*