Cell-like and Tissue-like Membrane Systems as Recognizer Devices

Cell-like and Tissue-like Membrane Systems as Recognizer Devices Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, Agust´ın Riscos-N´u˜nez, and Francisco J. Romero-Campero Research Group on Natural Computing Dpt. Computer Science and Artificial Intelligence, University of Sevilla, Sevilla, Spain ETS Ingenier´ıa Inform´atica, Avda. Reina Mercedes s/n {magutier,marper,ariscosn,fran}@us.es Abstract. Most of the variants of membrane systems found in the literature are generally thought as generating devices. In this paper recognizer computational devices (cell–like and tissue–like) are presented in the framework of Membrane Computing, using the biological membranes arranged hierarchically, inspired from the structure of the cell, and using the biological membranes placed in the nodes of a graph, inspired from the cell inter–communication in tissues. In this context, polynomial complexity classes of recognizer membrane systems are introduced. The paper also addresses the Pversus NP problem, and the (efficient) solvability of computationally hard problems, in the framework of these new complexity classes. 1 Introduction One of the main goals of a computing model is to solve problems. In order to design computational devices capable of attacking decision problems, we must decide how to represent by strings the instances of the problem. In that context, to solve a decision problem consists of recognizing the language associated with it. Membrane Computing is a young branch of Natural Computing providing distributed parallel computing models whose computational devices are called membrane systems, which are inspired by some basic biological features, by the structure and functioning of the living cells, as well as from the cooperation of cells in tissues, organs, and organisms. In this area there are basically two ways to consider computational devices: cell–like membrane systems and tissue–like membrane systems. The first one, using the biological membranes arranged hierarchically, inspired from the structure of the cell, and the second one using the biological membranes placed in the nodes of a graph, inspired from the cell inter–communication in tissues. In this paper we present recognizer membrane systems (both cell–like and tissue–like variants) as a framework to address ways to efficiently solving computationally hard problems, capturing the true concept of algorithm in spite of providing a non–deterministic computing model. 2 Preliminaries The computational devices of a model of computation are designed to handle inputs and outputs that are strings over a finite alphabet. Usually, NP-completeness has been studied in the framework of decision problems, but it is not an important restriction because one can easily transform any optimization problem into a 170 M.A. Guti´errez, M.J. P´erez, A. Riscos and F.J. Romero roughly equivalent decision problem by supplying a target value for the quantity to be optimized, and asking the question whether this value can be attained. Definition 1. A decision problem is a pair (I, θ) such that Iis a language over a finite alphabet (whose elements are called instances) and θis a total boolean function (that is, a predicate) over I. There exists a natural correspondence between languages and decision problems in the following way. Each language L, over an alphabet Σ, has a decision problem, XL, associated with it as follows: IXL=Σ∗, and θXL={(u, 1) |u∈L}∪{(u, 0) |u∈Σ∗−L}; reciprocally, given a decision problem X= (IX, θX), the language LXover the alphabet of IXcorresponding to it is defined as follows: LX={u∈IX|θX(u) = 1}. The Pversus NP problem is the problem of determining whether every problem solvable by some non-deterministic Turing machine in polynomial time can also be solved by some deterministic Turing machine in polynomial time. It is one of the outstanding open problems in theoretical computer science. A negative answer to this question would confirm that the majority of current cryptographic systems are secure from a practical point of view. A positive answer would not only show the uncertainty about the security of these systems, but also this kind of answer is expected to come together with a general procedure that provides a deterministic algorithm solving most of the NP–complete problems in polynomial time. In the last years several computing models using powerful tools from nature have been developed (because of this, they are known as bio-inspired models) and several solutions in polynomial time to problems from the class NP have been presented, making use of non-determinism and/or of an exponential amount of space. This is the reason why a practical implementation of such models (in biological, electronic, or other media) could provide a significant advance in the resolution of computationally hard problems. 3 Cell–like recognizer membrane systems In the structure and functioning of a cell, biological membranes play an essential role. The cell is separated from its environment by means of a skin membrane, and it is internally compartmentalized by means of internal membranes. The main syntactic ingredients of a cell–like membrane system are the membrane structure, the multisets, and the evolution rules. •Amembrane structure consists of several membranes arranged in a hierarchical structure inside a main membrane (the skin), and delimiting regions (the space in–between a membrane and the immediately inner membranes, if any). Each membrane identifies a region inside the system. A membrane structure can be considered as a rooted tree. •Regions defined by a membrane structure contain objects corresponding to chemical substances present in the compartments of a cell. The objects can be described by symbols or by strings of symbols, in such a way that multiset of objects are placed in regions of the membrane structure. •The objects can evolve according to given evolution rules, associated with the regions (hence, with the membranes). The semantics of the cell–like membrane systems is defined through a non deterministic and synchronous model (in the sense that a global clock is assumed) as follows: •Aconfiguration of a cell–like membrane system consists of a membrane structure and a family of multisets of objects associated with each region of the structure. At the beginning, there is a configuration called the initial configuration of the system. Cell–like and tissue–like membrane systems 171 •In each time unit we can transform a given configuration in another configuration by applying the evolution rules to the objects placed inside the regions of the configurations, in a non– deterministic, and maximally parallel manner (the rules are chosen in a non–deterministic way, and in each region all objects that can evolve must do it). In this way, we get transitions from one configuration of the system to the next one. •Acomputation of the system is a (finite or infinite) sequence of configurations such that each one is obtained from the previous one by a transition, and shows how the system is evolving. •A computation which reaches a configuration where no more rules can be applied to the existing objects, is called a halting computation. •The result of a halting computation is usually defined through the multiset associated with a specific output membrane (or the environment) in the final configuration. In the basic version, cell–like membrane systems can be seen as generating devices, working in a non–deterministic and maximally parallel manner, with output membrane, and without input membrane. But we are very interested in to use cell-like membrane systems in order to solve decision problems. What are the necessary ingredients to solve problems with a computational device? We will see that we must work with non–deterministic (but confluent) systems, using maximal parallelism, without output membrane (the output will be in the enviroment), and with input membrane. Definition 2. AP system with input is a tuple (Π, Σ, iΠ), where: (a) Πis a P system, with working alphabet Γ, with pmembranes labelled by 1,...,p, and initial multisets M1,...,Mpassociated with them; (b) Σis an (input) alphabet strictly contained in Γand the initial multisets are over Γ−Σ; and (c) iΠis the label of a distinguished (input) membrane. If mis a multiset over Σ, then the initial configuration of (Π, Σ, iΠ)with input mis (µ, M1,...,MiΠ∪ m,...Mp). Definition 3. Acell–like recognizer membrane system is a P system with input, (Π, Σ, iΠ), and with external output such that: (1) The working alphabet contains two distinguished elements YES, NO; (2) All computations halt; and (3) In every computation of Π, either some object YES or some object NO (but not both) must have been released into the environment, and only in the last step of the computation. We say that Cis an accepting (respectively, rejecting) computation if the object YES (respectively, NO) appears in the environment associated with the corresponding halting configuration of C. We denote by Rthe class of all cell–like recognizer membrane systems. We propose to solve a decision problem through a family of P systems (constructed in a uniform way) such that each element of the family processes all the instances of equivalent size, in some sense (we say that these solutions are uniform solutions). Next, we define what means to solve a decision problem in the framework of cell–like membrane systems, and in an uniform way. Definition 4. We say that a decision problem X= (IX, θX) is solvable in polynomial time by a family Π= (Π(n))n∈N, of R, and we denote this by X∈PMCR, if the following is true: •The family Πis polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine constructing Π(n) from n∈Nin polynomial time. •There exists a pair (cod, s) of polynomial-time computable functions whose domain is L, such that: –For each u∈L,s(u) is a natural number and cod(u) is an input multiset of Π(s(u)). 172 M.A. Guti´errez, M.J. P´erez, A. Riscos and F.J. Romero –The family Πis polynomially bounded with regard to (X, cod, s); that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(h(u)) with input g(u) is halting and, moreover, it performs at most p(|u|) steps. –The family Πis sound, with regard to (X, cod, s); that is, for each u∈IXit is verified that if there exists an accepting computation of Π(h(u)) with input g(u), then θX(u) = 1. –The family Πis complete with regard to (X, cod, s); that is, for each u∈IXit is verified that if θX(u) = 1, then every computation of Π(h(u)) with input g(u) is an accepting one. In the above definition we have imposed every P system Π(n) to be confluent, in the following sense: every computation with the same input produces the same output. We have the class PMCRis closed under polynomial–time reduction and complement. If systems without input membrane are used, constructing one specific system for each instance, but keeping the ‘polynomially uniform by Turing machines’ condition, then we say that the obtained solutions are semi–uniform. We shall denote by PMC∗ Rthe class of problems solvable in polynomial time by a semi–uniform family of systems in R. 4 The Pversus NP problem in the context of cell–like recognizer membrane systems We consider deterministic Turing machines as language recognizer devices. Then, we can associate with each deterministic Turing machine a decision problem, which will permit us to define when such a machine is simulated by a family of P systems (this issue was also addressed e.g. in [12,20]). Definition 5. Let Mbe a Turing machine with input alphabet ΣM. The decision problem associated with Mis the problem XM= (I, θ), where I=Σ∗ M, and for every w∈Σ∗ M,θ(w) = 1 if and only if Maccepts w. Obviously, the decision problem XMis solvable by the Turing machine M. Definition 6. We say that a Turing machine, M, is simulated in polynomial time by a family of systems of the class R, if XM∈PMCR. In cell–like membrane systems, evolution rules, communication rules and rules involving dissolution are called basic rules. That is, by applying this kind of rules the size of the membrane structure does not increase. Hence, it is not possible to construct an exponential working space in polynomial time using only basic rules in a cell–like membrane system. We recall here a result from Chapter 9 of [22]. Proposition 1. Let Mbe a deterministic Turing machine working in polynomial time. Then Mcan be simulated in polynomial time by a family of cell–like recognizer membrane systems using only basic rules. Reciprocally, in [20] the following result was proved: Proposition 2. For every decision problem solvable in polynomial time by a family of cell–like recognizer membrane systems using only basic rules, there exists a Turing machine solving it in polynomial time. Under the hypothesis P6=NP, Zandron et al. [23] established the limitations of cell-like membrane systems which use only basic rules concerning the efficient solution of NP-complete problems. This result was generalized by P´erez–Jim´enez et al. [20] obtaining the following two characterizations of the P6=NP relation by means of unsolvability results in polynomial time for NP–complete problems by families of cell–like recognizer membrane systems using only basic rules. Cell–like and tissue–like membrane systems 173 Theorem 1. The following propositions are equivalent: 1. P6=NP. 2. There exists an NP–complete decision problem unsolvable in polynomial time by a family cell– like recognizer membrane systems using only basic rules. 3. Each NP–complete decision problem is unsolvable in polynomial time by a family of cell–like recognizer membrane systems using only basic rules. Let us denote by RB the class of cell–like recognizer membrane systems using only basic rules. From the constructive proof given in [22], we deduce the following result characterizing the standard complexity class P. Theorem 2. P=PMCRB. 5 Recognizer cell–like membrane systems with active membranes A particularly interesting class of cell–like membrane systems are the systems with active membranes, where the membrane division can be used in order to solve computationally hard problems, e.g., NP-complete problems, in polynomial or even linear time, by a space–time trade-off. Definition 7. A recognizer cell–like membrane system with active membranes is a recognizer cell– like membrane system (Π, Σ, iΠ) where the rules of the associated P system are of the following forms (Hbeing the set of labels of Π): 1. [ a→ω]α hfor h∈H,α∈ {+,−,0},a∈Σ,ω∈Σ∗: An object awithin a membrane labelled with hand polarity α, evolves to a multiset ω. 2. a[ ]α1 h→[b]α2 hfor h∈H,α1, α2∈ {+,−,0},a, b ∈Σ: An object from the region immediately outside a membrane labelled with his introduced in this membrane, possibly transformed into another object, and simultaneously, the polarity of the membrane can be changed. 3. [ a]α1 h→b[ ]α2 hfor h∈H,α1, α2∈ {+,−,0},a, b ∈Σ: An object is sent out from membrane labelled with hto the region immediately outside, possibly transformed into another object, and simultaneously, the polarity of the membrane can be changed. 4. [ a]α h→bfor h∈H,α∈ {+,−,0},a, b ∈Σ: A membrane labelled with his dissolved in reaction with an object. The skin is never dissolved. 5. [ a]α1 h→[b]α2 h[c]α3 hfor h∈H,α1, α2, α3∈ {+,−,0},a, b, c ∈Σ: An elementary membrane can be divided into two membranes with the same label, possibly transforming some objects and their polarities. 6. [ [ ]α1 h1...[ ]α1 hk[ ]α2 hk+1 . . . [ ]α2 hm]α0 h0→[ [ ]α3 h1...[ ]α3 hk]α5 h0[[]α4 hk+1 ...[ ]α4 hm]α6 h0, for k≥1, m > k,hi∈Hfor 0 ≤i≤m, and α1,...,α6∈ {+,−,0}, with {α1, α2}={+,−}. These are division rules for non–elementary membranes. If the membrane with label h0contains other membranes than those with labels h1,...,hm, then they must have neutral charge in order to make this rule applicable; these membranes and their contents are duplicated and placed in both new copies of the membrane h0. Besides, every object in region h0, as well as all membranes and objects placed inside membranes h1,...,hm, are reproduced in the new copies of membrane h0. These rules are applied according to the following principles: •All the rules are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by only one rule (chosen in a non deterministic way), but any object which can evolve by one rule of any form, must evolve. 174 M.A. Guti´errez, M.J. P´erez, A. Riscos and F.J. Romero •If a membrane is dissolved, its content (multiset and internal membranes) is left free in the surrounding region. •If at the same time a membrane labelled by his divided by a rule of type (e) and there are objects in this membrane which evolve by means of rules of type (a), then we suppose that first the evolution rules of type (a) are used, and then the division is produced. Of course, this process takes only one step. •The rules associated with membranes labelled by hare used for all copies of this membrane. At one step, a membrane can be the subject of only one rule of types (b)-(e). Let us denote by AM the class of recognizer P systems with active membranes using 2-division. Different polynomial time solutions for NP–complete problems have been obtained using this class of cell–like recognizer membrane systems: Knapsack ( [14]), Subset Sum ( [13]), Partition ( [4]), SAT ( [19]), Clique ( [1]), Bin Packing ( [15]), and CAP ( [16]). Having in mind that the complexity class PMCAM is closed under complement and polynomial time reductions we have the following result. Proposition 3. NP ⊆PMCAM, and co-NP ⊆PMCAM. The complexity class PMCAM does not seem precise enough to describe classical complexity classes below NP. Therefore, it is challenging to investigate weaker variants of cell–like membrane systems able to characterize classical complexity classes. In [2] universality has been achieved by removing the polarization of membranes from P systems with active membranes but allowing the change of membrane labels. Several efficient solutions to NP–complete problems have been obtained within the following variant of membrane systems with active membranes: •P systems using 2–division for elementary membranes, without cooperation, without priorities, without label changing, but using only two electrical charges (A. Alhazov [2], A. Riscos [21]). •P systems using 2–division for elementary membranes, without cooperation, without priorities, without label changing, without polarizations, but using bi–stable catalysts (M.J. P´erez and F.J Romero [17]). •P systems without polarizations, without cooperation, without priorities, without label changing, without division, but using three types of membrane rules: separation, merging and release (L. Pan et al. [7]). •P systems with separation rules instead of division rules, in two different cases: (a) using polarizations and separation rules; and (b) without polarizations, but using separation rules with change of membrane labels (L. Pan and T.O. Ishdorj [8]). It is possible to obtain polynomial time solutions to NP–complete problems through cell–like recognizer membrane systems with active membranes using 2-division for elementary membranes. But, what happens if we remove polarizations? We denote by AM0the class of this kind of recognizer P systems. Question: What is exactly the class of decision problems solvable in polynomial time by families of systems belonging to AM0? We denote by AM0(α, β), where α∈ {−d, +d}and β∈ {−ne, +ne}, the class of all cell– like recognizer P systems with polarizationless active membranes such that: (a) if α= +d(resp. α=−d) then dissolution rules are permitted (resp. forbidden); and (b) if β= +ne (resp. β=−ne) then division rules for elementary and non–elementary (resp. only division rules for elementary) membranes are permitted. Proposition 4. For each α∈ {−d, +d}and β∈ {−ne, +ne}we have: (1) PMCAM0(α,β)⊆PMC∗ AM0(α,β). Cell–like and tissue–like membrane systems 175 (2) PMCAM0(α,−ne)⊆PMCAM0(α,+ne). (3) PMC∗ AM0(α,−ne)⊆PMC∗ AM0(α,+ne). (4) PMCAM0(−d,β)⊆PMCAM0(+d,β). (5) PMC∗ AM0(−d,β)⊆PMC∗ AM0(+d,β). In the framework of recognizer P systems with membrane division but without using polarizations it has been shown a surprising role of the dissolution rules, as it makes the difference between efficiency and non–efficiency for P systems with membrane division and without polarization ( [3,5]). Theorem 3. We have the following: (1) P=PMCAM0(−d,β)=PMC∗ AM0(−d,β), for each β∈ {−ne, +ne}. (2) NP ∪co −NP ⊆PMC∗ AM0(+d,+ne). (3) PSPACE ⊆PMCAM0(+d,+ne). 6 Tissue–like recognizer membrane systems with active membranes In this section we consider computational devices inspired from the cell inter–communication in tissues, and adding the ingredient of cell division rules of the same form as in cell–like membrane systems with active membranes, but without using polarizations. In these systems, the rules are used in the non-deterministic maximally parallel way, but we suppose that when a cell is divided, its interaction with other cells or with the environment is blocked; that is, if a division rule is used for dividing a cell, then this cell does not participate in any other rule, for division or communication. The set of communication rules implicitely provides the graph associated with the system through the labels of the membranes. The cells obtained by division have the same labels as the mother cell, hence the rules to be used for evolving them or their objects are inherited. Definition 8. Atissue–like membrane system with active membranes is a tuple Π= (Γ, Σ, M1,...,Mp, E, R, iin), where: 1. p≥1 (the initial degree of the system; the system contains pcells, labelled with 1,2,...,p); 2. Γis the working alphabet containing two distinguished objects YES and NO; 3. Σis an (input) alphabet strictly contained in Γ. 4. M1,...,Mpare multisets over Γ−Σ, describing the objects placed in the cells of the system (we suppose that at least one copy of YES and NO is in some of these multisets); 5. E⊆Γis the set of objects present in the environment in arbitrary many copies each (the objects YES and NO are not present in E); 6. Ris a finite set of developmental rules, of the following forms: (a) (i, u/v, j), for i, j ∈ {0,1,2, . . . , p}, i 6=j, and u, v ∈Γ∗; 1,2,...,p identify the cells of the system, 0 is the environment: When applying a rule (i, x/y, j), the objects of the multiset represented by uare sent from region ito region jand simultaneously the objects of the multiset vare sent from region jto region i; (b) [ a]i→[b]i[c]i, where i∈ {1,2, . . . , p}and a, b, c ∈Γ: Under the influence of object a, the cell with label iis divided in two cells with the same label; in the first copy the object ais replaced by b, in the second copy the object ais replaced by c; all other objects are replicated and copies of them are placed in the two new cells. 176 M.A. Guti´errez, M.J. P´erez, A. Riscos and F.J. Romero 7. iin ∈ {1, . . . , n}is the label of the input membrane. Let mbe a multiset over Σ. The initial configuration of Πwith input mis the tuple (M1,...,Miin ∪ m, . . . , Mp). The rules of a tissue–like membrane system as above are used in the non-deterministic maximally parallel manner as customary in membrane computing. In each step, we apply a set of rules which is maximal (no further rule can be added), with the following important restriction: if a cell is divided, then the division rule is the only one which is applied for that cell in that step, its objects do not participate in any communication rule. The computation starts from the initial configuration and proceeds as defined above; only halting computations give a result, and the result is given by the presence of a distinguished object in the environment. Definition 9. A tissue–like membrane system with active membranes Πis a recognizer system if: (a) all computations halt; and (b) in every computation of Π, either a copy of the object YES or a copy of the object NO (but not both) is sent into the environment. We say that Cis an accepting (rejecting) computation if the object YES (respectively, the object NO) appears in the environment associated with the corresponding halting configuration of C. We denote by T R the class of tissue–like recognizer membrane systems with active membranes. In order to present the concept of uniform solvability in the framework of membrane systems as above, we define the concept of polynomial encoding from a language in a family of tissue–like recognizer membrane systems with active membranes. Definition 10. Let Lbe a language, and Π= (Π(n))n∈Na family of tissue–like recognizer membrane systems of T R. A polynomial encoding of Lin Πis a pair (cod, s) of polynomial-time computable functions whose domain is L, and for each u∈L,s(u) is a natural number and cod(u) is an input multiset of the system Π(s(u)). In the present paper we are interested in the computing efficiency. That is why we have introduced a variant of tissue–like systems with membrane division. Next we define the concept of solvability in this new framework and in a similar way to Definition 4. Definition 11. We say that a decision problem X= (IX, θX) is solvable in polynomial time by a family Π= (Π(n))n∈N, of tissue–like recognizer membrane systems with active membranes, and we denote this by X∈PMCT R, if the following is true: •The family Πis polynomially uniform by Turing machines. •There exists a polynomial encoding (cod, s) from IXto Πsuch that the family Πis polynomially bounded, sound and complete with regard to (X, cod, s). We also have the class PMCT R is closed under polynomial–time reduction and complement. We have said nothing about the way the computations proceed; in particular, they can be non-deterministic, as standard in membrane computing. It is important however to remark that the systems always stop and they always send out an object which is the correct answer to the instance of the problem that they are processing. This natural extension of tissue P systems provides the possibility of solving SAT in polynomial time, in a confluent way: at precise times, one of the objects YES, NO is sent to the environment, giving the answer to the question whether the input propositional formula is satisfiable. We refer to [11] for a more detailed presentation of the following design. Let us consider a propositional formula ϕ=C1∧ · · · ∧ Cm, consisting of mclauses Cj= yj,1∨ · · · ∨ yj,kj, where yj,i ∈ {xl,¬xl|1≤l≤n}(there are used nvariables). Without loss of generality, we may assume that no clause contains two occurrences of some xior two occurrences Cell–like and tissue–like membrane systems 177 of some ¬xi(the formula is not redundant at the level of clauses), or both xiand ¬xi(otherwise such a clause is trivially satisfiable, hence can be removed). We consider the family Π={Π(hn, mi) : n, m ∈N}of tissue–like recognizer membrane systems, being hn, mi=(n+m)·(n+m+1) 2+n. The tissue–like recognizer membrane system Π(hn, mi)=(Γ(hn, mi), Σ(hn, mi),M1,M2, E(hn, mi), R(hn, mi), iin) will process all Boolean formulae in conjunctive normal form with nvariables and mclauses, and is defined as follows: Γ(hn, mi) = {ai, ti, fi|1≤i≤n}∪{ri|1≤i≤m} ∪ {Ti,1, Fi,1|1≤i≤n} ∪ {T0 i,j , F0 i,j |1≤i≤n, 1≤j≤m+ 1} ∪ {si,j , s0 i,j |1≤i≤n, 1≤j≤m} ∪ {bi|1≤i≤3n+m+ 1}∪{ci|1≤i≤n+ 1} ∪ {di|1≤i≤3n+nm +m+ 2}∪{ei|1≤i≤3n+nm +m+ 4} ∪ {f, g, Y ES, NO}, Σ(hn, mi) = {si,j , s0 i,j |1≤i≤n, 1≤j≤m}, M1=Y ES NO b1c1d1e1, M2=fga1a2...an, E(hn, mi) = Γ(hn, mi)− {Y ES, NO}, iin = 2, and the following rules. 1. [ ai]2→[Ti,1]2[Fi,1]2, for all i= 1,2, . . . , n. 2. (1, bi/b2 i+1,0),for all i= 1,2,...,n+ 1. 3. (1, ci/c2 i+1,0),for all i= 1,2,...,n+ 1. 4. (1, di/d2 i+1,0),for all i= 1,2,...,n+ 1. 5. (1, ei/ei+1,0),for all i= 1,2,...,3n+nm +m+ 3. 6. (1, bn+1cn+1/f, 2). 7. (1, dn+1/g, 2). 8. (2, cn+1Ti,1/cn+1T0 i,1,0). 9. (2, cn+1Fi,1/cn+1F0 i,1,0),for each i= 1,2,...,n. 10. (2, T0 i,j /tiT0 i,j+1,0). 11. (2, F0 i,j /fiF0 i,j+1,0),for each i= 1,2,...,n and j= 1,2,...,m. 12. (2, bi/bi+1,0). 13. (2, di/di+1,0), for all i=n+ 1, . . . , (n+ 1) + (2n+m)−1. 14. (2, b3n+m+1tisi,j /b3n+m+1rj,0). 15. (2, b3n+m+1fis0 i,j /b3n+m+1rj,0),for all 1 ≤i≤nand 1 ≤j≤m. 16. (2, di/di+1,0), for all i= 3n+m+ 1,...,(3n+m+ 1) + nm −1. 17. (2, d3n+nm+m+iri/d3n+nm+m+i+1,0), for all i= 1,2, . . . , m. 18. (2, d3n+nm+2m+1/f Y ES, 1). 19. (2, Y ES/λ, 0). 20. (1, e3n+nm+2m+2f NO/λ, 2). 21. (2, NO/λ, 0).