15th Brainstorming Week on Membrane Computing Sevilla, January 31 - February 3, 2017, RGNC REPORT 1/2017 Research Group on Natural Computing Sevilla University

15th Brainstorming Week on Membrane Computing Sevilla, January 31 – February 3, 2017 Carmen Graciani Gheorghe P˘aun Agust´ın Riscos-N´u˜nez Luis Valencia-Cabrera Editors 15th Brainstorming Week on Membrane Computing Sevilla, January 31 – February 3, 2017 Carmen Graciani Gheorghe P˘aun Agust´ın Riscos-N´u˜nez Luis Valencia-Cabrera Editors RGNC REPORT 1/2017 Research Group on Natural Computing Sevilla University F´enix Editora, Sevilla, 2017 c Autores ISBN: 978-84-946316-1-0 Edita: F´enix Editora [email protected] www.fenixeditora.com Telf. (+34) 954 40 74 36 Impreso en Espa˜na - Printed in Spain Preface The 15th Brainstorming Week on Membrane Computing (BWMC) was held in Sevilla, from January 31 to February 3, 2017, in the organization of the Research Group on Natural Computing (RGNC) from the Department of Computer Science and Artificial Intelligence of Sevilla University. The first edition of BWMC was organized at the beginning of February 2003 in Rovira i Virgili University, Tarragona, and all the next editions took place in Sevilla at the beginning of February, each year. The program was available at www.gcn.us.es/15bwmc program In the style of previous meetings in this series, the 15th edition of BWMC was conceived as a period of active interaction among the participants, with the emphasis on exchanging ideas and cooperation. Several “provocative” talks were delivered, mainly devoted to open problems, research topics, conjectures waiting for proofs, followed by an intense cooperation among the 23 participants – see the list in the end of this preface. The efficiency of this type of meetings was again proved to be very high and the present volume illustrates this assertion. The present volume is meant to be a working instrument, part of the interaction started during the stay of authors in Sevilla, making possible a further cooperation, this time having a written support. A selection of papers from this volume will be considered for publication in special issues of Theoretical Computer Science. After each BWMC, one or two special issues of various international journals were published. Here is their list: •BWMC 2003: Natural Computing – volume 2, number 3, 2003, and New Generation Computing – volume 22, number 4, 2004; •BWMC 2004: Journal of Universal Computer Science – volume 10, number 5, 2004, and Soft Computing – volume 9, number 5, 2005; •BWMC 2005: International Journal of Foundations of Computer Science – volume 17, number 1, 2006); •BWMC 2006: Theoretical Computer Science – volume 372, numbers 2-3, 2007; vi Preface •BWMC 2007: International Journal of Unconventional Computing – volume 5, number 5, 2009; •BWMC 2008: Fundamenta Informaticae – volume 87, number 1, 2008; •BWMC 2009: International Journal of Computers, Control and Communication – volume 4, number 3, 2009; •BWMC 2010: Romanian Journal of Information Science and Technology – volume 13, number 2, 2010; •BWMC 2011: International Journal of Natural Computing Research – volume 2, numbers 2-3, 2011. •BWMC 2012: International Journal of Computer Mathematics – volume 99, number 4, 2013. •BWMC 2013: Romanian Journal of Information Science and Technology, vol. 17, nr. 1, 2014. •BWMC 2014: Fundamenta Informaticae, volume 134, numbers 1-2, 2014. •BWMC 2015: Natural Computing – volume 15, issue 4, 2016 (some papers from ACMC 2015 were also selected for this special issue). •BWMC 2016: Theoretical Computer Science – in press (some papers from ACMC 2016 were also selected for this special issue). Some of the papers elaborated during the 15th BWMC were submitted to various journals and conferences. The reader interested in the final version of these papers is advised to check the current bibliography of membrane computing available in the domain website http://ppage.psystems.eu. *** The list of participants as well as their email addresses are given below, with the aim of facilitating the further communication and interaction: 1. Jos´e Antonio Andreu-Guzm´an, Universidad de Sevilla (Spain) [email protected] 2. Lucie Ciencialov´a, Silesian University (Opava, Czech Republic) [email protected] 3. Rudolf Freund, Technological University of Vienna (Austria) [email protected] 4. Carmen Graciani, Universidad de Sevilla (Spain) [email protected] 5. Sergiu Ivanov, Universit´e Paris-Est Cr´eteil (France) [email protected] 6. G´abor Kolonits, E¨otv¨os Lor´and University (Hungary) [email protected] 7. Alberto Leporati, University of Milan-Bicocca (Italy) [email protected] 8. Francisco J. Mac´ıas-Garc´ıa, Universidad de Sevilla (Spain) [email protected] Preface vii 9. Luca Manzoni, University of Milan-Bicocca (Italy) [email protected] 10. Miguel A. Mart´ınez-del-Amor, Universidad de Sevilla (Spain) [email protected] 11. David Orellana-Mart´ın, Universidad de Sevilla (Spain) [email protected] 12. Ignacio Prez-Hurtado, Universidad of Seville (Spain) [email protected] 13. Mario de J. P´erez-Jim´enez, Universidad de Sevilla (Spain) and Academia Europaea [email protected] 14. Antonio Enrico Porreca, University of MilanBicocca (Italy) [email protected] 15. Fernando Rendn-Segador, Universidad de Sevilla (Spain) [email protected] 16. Agust´ın Riscos-N´u˜nez, Universidad de Sevilla (Spain) [email protected] 17. Daniel Rodr´ıguez-Chavarr´ıa, Universidad de Sevilla (Spain) [email protected] 18. ´ Alvaro Romero-Jim´enez, Universidad de Sevilla (Spain) [email protected] 19. Eduardo S´anchez-Karhunen, Universidad de Sevilla (Spain) [email protected] 20. Jose Mar´ıa Sempere-Luna, Politechnical University of Valencia (Spain) [email protected] 21. Luis Valencia-Cabrera, Universidad de Sevilla (Spain) [email protected] 22. Gyorgy Vaszil, University of Debrecen (Hungary) [email protected] 23. Lian Ye, Chongqing University (China) [email protected] As mentioned above, the meeting was organized by the Research Group on Natural Computing from Sevilla University (http://www.gcn.us.es)– and all the members of this group were enthusiastically involved in this (not always easy) work. The meeting was partially supported by Universidad de Sevilla, more precisely by Department of Computer Science and Artificial Intelligence and VI Plan Propio, Vicerrectorado de Investigaci´on de la Universidad de Sevilla. Carmen Graciani Gheorghe P˘aun Agust´ın Riscos-N´u˜nez Luis Valencia-Cabrera (August 2017) Contents Unfair P Systems A. Alhazov, R. Freund, S. Ivanov ........................................ 1 P Systems with Randomized Right-hand Sides of Rules A. Alhazov, R. Freund, S. Ivanov ....................................... 13 Time-freeness and Clock-freeness and Related Concepts in P Systems A. Alhazov, R. Freund, S. Ivanov, L. Pan, B. Song ..................... 43 Membrane Systems and Time Petri Nets B. Aman, P. Batty´anyi, G. Ciobanu, G. Vaszil ......................... 71 Two Notes on APCol Systems L. Ciencialov´a L. Cienciala ............................................ 95 Subroutines in P Systems and Closure Properties of Their Complexity Classes A. Leporati, L. Manzoni, G. Mauri, A.E. Porreca, C. Zandron ......... 115 On Efficiency of P Systems with Symport/Antiport and Membrane Division L.F. Mac´ıas-Ramos, B. Song, T. Song, L. Pan, M.J. P´erez-Jim´enez . . . 129 Limits on Efficient Computation in P Systems with Symport/Antiport Rules L.F. Mac´ıas-Ramos, B. Song, T. Song, L. Pan, M.J. P´erez-Jim´enez . . . 147 Sparse-matrix Representation of Spiking Neural P Systems for GPUs M. ´ A. Mart´ınez-del-Amor, D. Orellana-Mart´ın, F.G.C. Cabarle, M.J. P´erez-Jim´enez, H.N. Adorna..................... 161 P Systems with Active Cells D. Orellana-Mart´ın .................................................... 175 6 A. Alhazov, R. Freund, S. Ivanov We observe that the effect is similar to that of controlling the application of rules by the well-known control mechanism called label selection, e.g., see [4], where either the rule with label 1 or the rule with label 2 has to be chosen. We will return to this model in Section 4.3.  The following weird example shows that the fairness function should be chosen from a suitable class of (at least recursive) functions, as otherwise the whole computing power comes from the fairness function: Example 3. Take the fair P system Π3with one membrane working in the maximally parallel way, starting with the axiom aand using the three rules 1 : a→aa, 2 : a→a, and 3 : a→b, see Figure 3. 1 : a→aa 2 : a→a 3 : a→b a;fM 1 Fig. 3. The P system Π3 Moreover, let M⊂N+, i.e., an arbitrary set of positive natural numbers. The fairness function fMon multisets of rules over these three rules and a configuration containing msymbols ais defined as follows: For any multiset of rules Rcontaining copies of the rules 1 : a→aa, 2 : a→a, and 3 : a→b, •f(R) = 0 if Ronly contains mcopies of rule 3 and m∈M, •f(R) = 0 if Ronly contains exactly one copy of rule 1 and the rest are copies of rule 2, •f(R) = 1 for any other applicable multiset of rules. Again the choice is made by applying only multisets of rules which yield the minimal value f(R) = 0. If we use rule 1 : a→aa once and rule 2 : a→afor the rest, this increases the number of symbols ain the skin membrane by one. Thus, in m−1 steps we get msymbols a. If m is in M, we now may use rule 3 : a→b for all symbols a, thus obtaining m symbols b, and the system halts. In that way, the system generates exactly {bm|m∈M}. To make this example a little bit less weird, we may only allow computable sets M. Still, the whole computing power is in the fairness function fMalone, with fMonly depending on the multiset of rules.  We now again return to Example 2 and illustrate how the same result can be obtained by using another fairness function in the standard unfair mode using the multsets of rules with minimal fairness value; on the other hand, we will also show what happens if we try to be fair and use the rules in a balanced way. Unfair P Systems 7 Example 4. Consider the P system Π1= ({a, b},{b},[1]1, a, R1,1) with the rule set R1={1 : a→aa, 2 : a→b}as considered in Example 1 together with the fairness function f4(R) for any multiset Rof rules defined as follows: consider f4(R) = |str(R)|, i.e., f4(R) is the number of different strings representing the multiset R. The resulting fair P system Π4= (Π1, f4) = ({a, b},{b},[1]1, a, R1,1, f4) is depicted in Figure 4. 1 : a→aa 2 : a→b a;f4 1 Fig. 4. The P system Π4 With the standard selection of multisets of rules to be applied by choosing those with the minimal value of the fairness function, we obtain the same result for the set of multisets generated by Π4, i.e., {a2n|n∈N}, because only the pure multisets of rules Rcontaining only copies of rule 1 or only copies of rule 2 yield f(R) = 1, whereas any mixed multiset of rules containing both rules at least once yields a bigger value. On the other hand, if we try to be fair and use both rules in a balanced way, i.e., by choosing those multisets of rules yielding the maximum values of f4, then the generated set is the singleton {b}, which can be generated in one step from the axiom aby using rule 2 : a→b. Any other derivation starting with using rule 1 : a→aa will not yield any result due to running into an infinite computation without any chance to halt: as soon as aa has been generated, only once the rule 1 : a→aa and once the rule 2 : a→bcan be used as only this combination of rules yields f4(h1,2i) = |{12,21}| = 2 >1 = f4(h1,1i) = f4(h2,2i) (we here use the brackets h,ito describe a multiset).  The problem with halting observed in the example above when using only non-cooperative rules seems to be an inherent one when using a fair (balanced) selection of multisets of rules. These variants may deserve further investigations in the future, but in this paper we will restrict ourselves to the standard (maximally unfair) selection of multisets of rules to be applied as in the previous examples. 4 First Results In this section, we show three general results. The first one describes how priorities can be simulated by a suitable fairness function in P systems of any kind working in the sequential mode. The second one exhibits how P systems with energy control, see [1], can be simulated by suitable fair P systems for any arbitrary derivation 8 A. Alhazov, R. Freund, S. Ivanov mode. Finally we show how P systems with rule label control, see [4], can be simulated by suitable fair P systems for any arbitrary derivation mode. 4.1 Simulating Priorities in the Sequential Derivation Mode In the sequential derivation mode, exactly one rule is applied in every derivation step of the P system Π. Given a configuration Cand the set of applicable rules Appl(Π, C) not taking into account a given priority relation <on the rules, we define the fairness function to yield 0 for each rule in Appl(Π, C) for which no rule in Appl(Π, C) with higher priority exists, and 1 otherwise. Thus, only a rule with highest priority can be applied. More formally, this result now is proved for any kind of P systems working in the sequential derivation mode: Theorem 1. Let (Π, <)be a P system of any kind with the priority relation <on its rules and working in the sequential derivation mode. Then there exists a fair P system (Π, f)with fairness function fsimulating the computations in (Π, <) selecting the multisets of rules with minimal values. Proof. First we observe that the main ingredient Πis exactly the same in both (Π, <) and (Π, f), i.e., we only replace the priority relation <by the fairness function f. As already outlined above, for any configuration Cof Πwe now define ffor any rule ras follows (we point out that here the fairness function not only depends on {r}, but also on Appl(Π, C)): •f(Appl(Π, C),{r}) = 0 if and only if there exists no rule r0∈Appl(Π, C) such that r < r0, and •f(Appl(Π, C),{r}) = 1 if and only if there exists a rule r0∈Appl(Π, C) such that r < r0. If we now define the task of fas choosing only those rules with minimal value, i.e., a rule rcan be applied to configuration Cif and only if f(Appl(Π, C),{r}) = 0, then we obtain the desired result.  4.2 Simulating Energy Control Recently we have considered P systems where a specific amount of energy is assigned to each rule, see [1]. There, only those multisets of rules are applied which use the minimal amount of energy. In a similar way the amount of energy coming up with a multiset of rules can be seen as the value of the fairness function. The minimal amount of energy then exactly corresponds with the minimal fairness. In this paper, from the two variants of energy-controlled P systems we only consider the one where the energy is directly assigned to the rules. This variant of P systems is called a rule energy-controlled P system. The multisets or sets of rules to be applied to a given configuration must fulfill the condition of yielding the minimal amount of energy. Unfair P Systems 9 Formally, in a rule energy-controlled P system the rules are of the form (p, v) where pis a rule of a specific type like cooperative or non-cooperative and vis an integer energy value. The total energy value of a mutiset of rules can be defined in different ways, but in the following we will assume it to simply be the sum of energy values of the rules in the multiset and denote this function computing the energy value of a multiset of rules in this way by σ. Theorem 2. Let (Π, σ)be a rule energy-controlled P system working in any derivation mode, using any kind of rules and using the sum function σfor computing the energy value of a multiset of rules. Then there exists a fair P system (Π0, f) with fairness function fsimulating the computations in (Π, σ)with fselecting the multisets of rules with minimal values. Proof. By definition, in the rule energy-controlled P system (Π, σ) a multiset of rules can be applied to given configuration only if the application of σyields the minimal value in Z. The fair P system (Π0, f) with fairness function fnow is constructed from (Π, σ) by replacing any rule with energy (p, v) by the rule p itself, but on the other hand defining the fairness function ffor a multiset of rules to take vas the value assigned to the rule phaving been obtained from (p, v). By summing up these values for the whole multiset and selecting only those multisets of rules applicable to a given configuration in the given derivation mode which have minimal values, ffulfills the same task in (Π0, f) as σdoes in (Π, σ). Hence, in any derivation mode, (Π0, f) simulates exactly step by step the derivations in (Π, σ), obviously yielding the same computation results.  4.3 Simulating Label Selection In P systems with label selection only rules belonging to one of the predefined subsets of rules can be applied to a given configuration, see [4]. For all the variants of P systems defined in Section 2, we may consider to label all the rules in the sets R1, . . . , Rmin a one-to-one manner by labels from a set H and to take a set Wcontaining subsets of H. Then a P system with label selection is a construct Πls = (O, T, µ, w1, . . . , wn, R1,...Rn, hi, ho, H, W ), where Π= (O, T, µ, w1, . . . , wn, R1,...Rn, hi, ho) is a P system as in Section 2, His a set of labels for the rules in the sets R1, . . . , Rm, and W⊆2H. In any transition step in Πls we first select a set of labels U∈Wand then apply a non-empty multiset Rof rules applicable in the given derivation mode restricted to rules with labels in U. The following proof exhibits how the fairness function can also be used to capture the underlying derivation mode. 10 A. Alhazov, R. Freund, S. Ivanov Theorem 3. Let (Π, H, W)be a P system with label selection using any kind of rules in any kind of derivation mode. Then there exists a fair P system (Π0, f) with fairness function fsimulating the computations in (Π, H, W)with fselecting the multisets of rules with minimal values. Proof. By definition, in the P system (Π, H, W ) with label selection a multiset of rules can be applied to given configuration only if all the rules have labels in a selected set of labels U∈W. We now consider the set of all multisets of rules applicable to a configuration C, denoted by Applasyn(Π, C), as it corresponds to the asynchronous derivation mode (abbreviated asyn); from those we select all R which obey to the label selection criterion, i.e., there exists a U∈Wsuch that the labels of all rules in Rbelong to U, and then only take those which also fulfill the criteria of the given derivation mode restricted to rules with labels from U. Hence we define (Π0, f) by taking Π0=Πand, for any derivation mode δ,fδ for any multiset of rules R∈Applasyn(Π, C) as follows: •fδ(C, Applasyn(Π, C), R) = 0 if there exists a U∈Wsuch that the labels of all rules in Rbelong to U, and, moreover, R∈Applδ(ΠU, C), where ΠUis the restricted version of Πonly containing rules with labels in U, as well as •fδ(C, Applasyn(Π, C), R) = 1 otherwise. According to our standard selection criterion, we choose only those multisets of rules where the fairness function yields the minimal value 0, i.e., those Rsuch that there exists a U∈Wsuch that the labels of all rules in Rbelong to Uand Ris applicable according to the underlying derivation mode with rules restricted to those having a label in U, which exactly mimicks the way of choosing Rin (Π, H, W ). Therefore, in any derivation mode δ, (Π0, fδ) simulates exactly step by step the derivations in (Π, H, W ), obviously yielding the same computation results.  5 Conclusions and Future Research In this article, we introduced and partially studied P systems with the application of rules in each step being controlled by a function on the applicable multisets of rules. We have given several examples exhibiting the power of using suitable fairness functions. Moreover, we have shown how priorities can be simulated by a suitable fairness function in P systems of any kind working in the sequential mode as well as how P systems with energy control or label selection can be simulated by fair P systems with a suitable fairness function for any derivation mode. Yet with all these examples and results we have just given a glimpse on what could be investigated in the future for P systems in connection with fairness functions: Unfair P Systems 11 •consider other variants of hierarchical P systems working in different derivation modes, e.g., also taking into consideration the set derivation modes; •extend the notion of fair to tissue P systems, i.e., P systems on an arbitrary graph structure; •extend the notion of fair to P systems with active membranes, there probably also controlling the division of membranes; •investigate the effect of selecting the multiset of rules to be applied to a given configuration by other criteria than just taking those yielding the minimal values for the fairness function; •consider other variants of fairness functions, either less powerful or taking into account other features of Appl(Π, C) and/or the multiset of rules R; •investigate the effect of selecting the multiset to be applied to a given configuration by requiring it to contain a balanced (really fair) amount of copies of each applicable rule; •show similar simulation results with suitable fairness functions as in Section 4 for other control mechanisms used in the area of P systems; •. . . References 1. Artiom Alhazov, Rudolf Freund, and Sergiu Ivanov. Variants of energy-controlled P systems. In Proceedings NIT 2016, 2016. 2. Rudolf Freund. P systems working in the sequential mode on arrays and strings. In Cristian Calude, Elena Calude, and Michael J. Dinneen, editors, Developments in Language Theory, 8th International Conference, DLT 2004, Auckland, New Zealand, December 13-17, 2004, Proceedings, volume 3340 of Lecture Notes in Computer Science, pages 188–199. Springer, 2004. 3. Rudolf Freund, Alberto Leporati, Giancarlo Mauri, Antonio E. Porreca, Sergey Verlan, and Zandron. Flattening in (tissue) P systems. In Artiom Alhazov, Svetlana Cojocaru, Marian Gheorghe, Yurii Rogozhin, Grzegorz Rozenberg, and Arto Salomaa, editors, Membrane Computing, volume 8340 of Lecture Notes in Computer Science, pages 173– 188. Springer, 2014. 4. Rudolf Freund, Marion Oswald, and Gheorghe P˘aun. Catalytic and purely catalytic P systems and P automata: Control mechanisms for obtaining computational completeness. Fundamenta Informaticae, 136(1-2):59–84, 2015. 5. Gheorghe P˘aun. Computing with Membranes. Journal of Computer and System Sciences, 61:108–143, 1998. 6. Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA, 2010. 7. Grzegorz Rozenberg and Arto Salomaa, editors. Handbook of Formal Languages, 3 volumes. Springer, New York, NY, USA, 1997. 8. Bulletin of the International Membrane Computing Society (IMCS). http:// membranecomputing.net/IMCSBulletin/index.php. 9. The P Systems Website. http://ppage.psystems.eu/. P Systems with Randomized Right-hand Sides of Rules Artiom Alhazov1,2?, Rudolf Freund3, and Sergiu Ivanov4,5 1Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au, MD-2028, Moldova [email protected] 2Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China School of Automation, Huazhong University of Science and Technology Wuhan 430074, China 3Faculty of Informatics, TU Wien Favoritenstraße 9–11, 1040 Vienna, Austria [email protected] 4LACL, Universit´e Paris Est – Cr´eteil Val de Marne 61, av. G´en´eral de Gaulle, 94010, Cr´eteil, France [email protected] 5TIMC-IMAG/DyCTiM, Faculty of Medicine of Grenoble 5 avenue du Grand Sablon, 38700, La Tronche, France [email protected] Summary. P systems are a model of hierarchically compartmentalized multiset rewriting. We introduce a novel kind of P systems in which rules are dynamically constructed in each step by non-deterministic pairing of left-hand and right-hand sides. We define three variants of right-hand side randomization and compare each of them with the power of conventional P systems. It turns out that all three variants enable non-cooperative P systems to generate exponential (and thus non-semi-linear) number languages. We also give a binary normal form for one of the variants of P systems with randomized rule right-hand sides. Finally, we also discuss extensions of the three variants to tissue P systems, i.e., P systems on an arbitrary graph structure. ?The work is supported by National Natural Science Foundation of China (61320106005 and 61033003) and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012). 14 A. Alhazov, R. Freund, S. Ivanov 1 Introduction Membrane computing is a research field originally founded by Gheorghe P˘aun in 1998, see [13]. Membrane systems (also known as P systems) are a model of computing based on the abstract notion of a membrane. Formally, a membrane is treated as a container delimiting a region; a region may contain objects which are acted upon by the rewriting rules associated with the membranes. Quite often, the objects are plain symbols coming from a finite alphabet, but P systems operating on more complex objects (e.g., strings, arrays) are often considered, too, e.g., see [9]. A comprehensive overview of different flavors of membrane systems and their expressive power is given in the handbook which appeared in 2010, see [14]. For a state of the art snapshot of the domain, we refer the reader to the P systems website [17], as well as to the bulletin of the International Membrane Computing Society [16]. Dynamic evolution of the set of available rules has been considered from the very beginning of membrane computing. Already in 1999, generalized P systems were introduced in [8]; in these systems the membranes, alongside the objects, contain operators which act on these objects, while the P system itself acts on the operators, thereby modifying the transformations which will be carried out on the objects in the subsequent steps. Among further ideas on dynamic rules, one may list rule creation [4], activators [1], inhibiting/deinhibiting rules [7], and symport/antiport of rules [6]. One of the more recent developments in this direction are polymorphic P systems [2, 3, 12], in which rules are defined by pairs of membranes, whose contents may be modified by moving objects in or out. We remark that the previous studies on dynamic rule sets either treated the rules as atomic entities (symport/antiport of rules, operators in generalized P systems), or allowed virtually unlimited possibilities of tampering with their shape (polymorphic P systems). In the present work, we propose a yet different approach which can be seen as an intermediate one. In P systems with randomized rule-right-hand sides (or with randomized RHS, for short), the available left-hand sides and right-hand sides of rules are fixed, but the associations between them are re-evaluated in every step: a left-hand side may pick a right-hand side arbitrarily (randomly). In Section 3, we present three different formal definitions of this intuitive idea of randomized RHS: 1. rules exchange their RHS, 2. each rule randomly picks an RHS from a common collection of RHS, shared between the rules, 3. each rule randomly picks an RHS from a possible collection of RHS associated with the rule itself. P systems with randomized RHS may have a real-world (possibly biological) application for representing systems in a hostile environment. The modifications such P systems effect on their rules may be used to represent perturbations caused P Systems with Randomized Rules 15 by the environment (mutations), somewhat in the spirit of faulty Turing machines (e.g., see [5]). In this article, we will focus on the expressive power of P systems with randomized RHS, as well as on comparing them to the classical model with or without cooperative rules. One of the central conclusions of the present work is that noncooperative P systems with randomized RHS can generate exponential number languages, thus (partially) surpassing the power of conventional P systems. This paper is structured as follows. Section 2 recalls some preliminaries about multisets, strings, permutations, as well as conventional P systems. Section 3 defines the three variants of RHS randomization. Section 4 discusses the computational power of the three variants of P systems with randomized RHS. Section 5 shows a binary normal form for one of the variants of P systems with randomized RHS. Section6 discusses extensions of the three variants of RHS randomization to tissue P systems. Finally, Section 7 summarizes the results of the article and gives some directions for future work. 2 Preliminaries In this paper, the set of positive natural numbers {1,2, . . . }is denoted by N+, the set of natural numbers also containing 0, i.e., {0,1,2, . . . }, is denoted by N. Given k∈N+, we will call the set N+k={x∈N+|1≤x≤k}an initial segment of N+. An alphabet Vis a finite set. The families of recursively enumerable, contextfree, linear, and regular languages, and of languages generated by tabled Lindenmayer systems are denoted by RE,CF,LIN,REG, and ET0L, respectively. The families of sets of Parikh vectors as well as of sets of natural numbers (multiset languages over one-symbol alphabets) obtained from a language family Fare denoted by PsF and NF, respectively. For further introduction to the theory of formal languages and computability, we refer the reader to [14, 15]. 2.1 Linear Sets over N Alinear set over Ngenerated by a set of vectors A={ai|1≤i≤d} ⊂fin Nn (here A⊂fin Bindicates that Ais a finite subset of B) and an offset a0∈Nnis defined as follows: hA, a0iN=(a0+Xd i=1 kiai ki∈N,1≤i≤d). If the offset a0is the zero vector 0, we call the corresponding linear set homogeneous; we also use the short notation hAiN=hA, 0iN. We use the notation NnLINN={hA, a0iN|A⊂fin Nn,a0∈Nn}, to refer to the class of all linear sets of n-dimensional vectors over N. Semi-linear sets are 22 A. Alhazov, R. Freund, S. Ivanov 3. construct the set of rules Rito be applied in membrane iby combining the left- and right-hand sides from l0 iand r0 i: Ri=set(l0 i→r0 i). In step (3), we combine the strings l0 iand r0 iusing the operator →defined in Subsection 2.4 and then apply the operator set to obtain the corresponding set of rules from the string representation. After having constructed the set Rifor each membrane i,Πwill proceed to applying the obtained rules according to the usual maximally parallel semantics. When computing the strings l0 iand r0 i, we apply two different permutations σl and σrto liand ri, in order to ensure fairness for the participation of left-hand and right-hand sides when |li| 6=|ri|. For example, if we only permuted riin the case in which |li|>|ri|, the left-hand sides located at positions k > |ri|in liwould never be used. We do not explicitly prohibit repetitions in lior in ri, but we avoid repeated rules by constructing Riusing the set function. Example 7. Consider the following P system with randomized pools of RHS: Π3= ({a, b},{b},[1]1, a, H, 1), with H=(a),(aa)(b); (a) stands for the multiset containing an instance of a, while (aa)(b) is the string denoting the two multisets (aa) and (b). The graphical representation of Π3is given in Figure 3. a aa b a1 Fig. 3. The P system Π3with randomized pools of RHS generating the number language {2n|n∈N}. The pair H= (l, r) of strings of multisets is represented by listing the multisets of land rin two columns and by drawing a vertical line between the two columns. Π3follows exactly the same pattern as Π2from Example 6: while the identity permutation is applied to r,Π3keeps doubling the symbols ain the skin. Once the multisets (aa) and (b) are permuted in r, and thus the rule a→bis formed, all symbols aare rewritten into symbols bin one step and Π3must halt. Note that randomly taking the right-hand sides from a given pool avoids having the extra dummy rule c→bin Π2. We will use the notation OPn(rhsPools, coo) to denote the family of P systems with randomized pools of RHS, with at most n membranes, with cooperative rules. To denote the family of such P systems with P Systems with Randomized Rules 23 non-cooperative rules, we replace coo by ncoo. To denote the family of languages of multisets generated by these P systems, we prepend Ps to the notation, and to denote the family of the generated number languages, we prepend N. 3.3 Variant 3: Individual Randomized RHS In this variant of P systems, each rule is constructed from a left-hand side and a set of possible right-hand sides. AP system with individual randomized RHS is a construct Π= (O, T, µ, w1, . . . , wn, P1,...Pn, ho), where Piis the set of productions associated with the membrane iand the other components of the tuple are defined as in the classical model (Section 2.5). A production is a pair u→R, where u∈O◦is the left-hand side and R⊆O◦ is a finite set of right-hand sides. The right-hand sides in Rmay have target indications, i.e., for a production in membrane i, we may consider R⊆(O× Tari)◦. At the beginning of each computation step, for every membrane i, for each production u→R∈Ri,Πwill non-deterministically (randomly) pick a right-hand side vfrom Rand will construct the rule u→v(this happens once per production). Πwill then apply the rules thus constructed according to the maximally parallel semantics. Example 8. Generating the language of the powers of two is the easiest compared with Variants 1 and 2. Indeed, consider the P system with individual randomized RHS Π4= ({a, b},{b},[1]1, a, P, 1) with only one production: P={a→ {aa, b})}. Its graphical representation is given in Figure 4. a→ {aa, b} a1 Fig. 4. The P system Π4with individual randomized RHS generating the number language {2n|n∈N}. Π4works exactly like Π2and Π3from Examples 6 and 7: it doubles the number of symbols aand halts by rewriting them to bin the last step. We will use the notation OPn(rndRhs, coo) to denote the family of P systems with individual randomized RHS, with at most nmembranes, with cooperative rules. To denote the family of such P systems with non-cooperative rules, we replace coo by ncoo. To denote the family of languages 24 A. Alhazov, R. Freund, S. Ivanov of multisets generated by these P systems, we prepend Ps to the notation, and to denote the family of the generated number languages, we prepend N. We will sometimes want to set an upper bound kon the number of righthand sides per production. To refer to the family of P systems with individual randomized RHS with such an upper bound, we will replace rndRhs by rndRhsk in the notation above. 3.4 Halting with Randomized RHS The conventional (total) halting condition for P systems can be naturally lifted to randomized RHS: a P system Πwith randomized RHS (Variant 1, 2, or 3) halts on a configuration Cif, however it permutes rule right-hand sides in Variant 1, or however it builds rules out of the available rule sides in Variants 2 and 3, no rule can be applied in C, in any membrane. Note that, for Variants 1 and 3, the permutations chosen do not affect the applicability of rules, because applicability only depends on left-hand sides, which are always the same in any membrane. The situation is different for Variant 2, because the number of available left-hand sides in a membrane of Πmay be bigger than the number of available right-hand sides. Therefore, if Πis a P system with randomized pools of RHS, the way rule sides are permuted may affect the number of rules applicable in a given configuration. This is why, for Πto halt on C, we require no rule to be applicable for any permutation. In this paper, we will mainly consider P systems with randomized pools of RHS in which, in every membrane, there are at least as many right-hand sides as there are left-hand sides. To refer to P systems with this restriction, we will use the notation rhsPools0. In these systems, the problem with the applicability of rules as described above can be avoided. 3.5 Equivalence Between Variants 1 and 2 Before discussing the computational power of the P systems with randomized RHS in general, we will briefly point out a strong relationship between P systems with random RHS exchange and P systems with randomized pools of RHS, with the restriction that every membrane contains at least as many right-hand sides as it has left-hand sides, i.e., for P systems with randomized RHS of type rhsPools0. Theorem 1. For any k∈ {coo, ncoo}, the following holds: PsOPn(rhsExchange, k) = PsOPn(rhsPools0, k). Proof. Any membrane with random RHS exchange trivially can be transformed into a membrane with randomized pools of RHS by listing the left-hand sides of the rules in the pool of LHS and the right-hand sides of the rules in the pool of RHS. P Systems with Randomized Rules 25 Conversely, consider a membrane iwith randomized pools of RHS, with the string liof LHS and the string riof RHS, |li|≤|ri|. We can transform it into a membrane with random RHS exchange as follows. For every LHS ufrom li, pick (and remove) an RHS vfrom ri, and construct the rule u→v. According to our supposition, we will exhaust the LHS before (or at the same time as) the RHS. For every RHS v0which is left, we add a new (dummy) symbol z0to the alphabet, and add the rule z0→v0. Since the symbol z0is new and does not appear in any RHS, it will never be produced and the rule z0→v0will essentially serve as a stash for the RHS v0. 3.6 Flattening The folklore flattening construction (see [14] for several examples as well as [10] for a general construction) is quite directly applicable to P systems with individual randomized RHS. Proposition 1 (flattening). For any k∈ {coo, ncoo}, the following is true: PsOP1(rndRhs, k) = PsOPn(rndRhs, k). Proof (sketch). Since in the case of individual randomized RHS, randomization has per rule granularity (whereas in the other two variants randomization occurs at the level of membranes), we can simulate multiple membranes by attaching membrane labels to symbols. For example, a production ab → {cd, f}in membrane hbecomes ahbh→ {chdh, fh}, while the send-in production a→ {(b, ini),(b, inj)}becomes ah→ {bi, bj}. On the other hand, for Variants 1 and 2 similar results cannot be proved in such a way, a situation which happens very seldom in the area of P systems, especially in the case of variants of the standard model. Yet intuitively, it is easy to understand why this happens, as in both Variants 1 and 2 the right-hand sides in just one membrane can randomly be chosen for any left-hand side, whereas different membranes can separate the possible combinations of left-hand sides and right-hand sides of rules. A formal proof showing that flattening is impossible for the types rhsExchange and rhsPools0will be given in the succeeding section by constructing a suitable example. 4 Computational Power of Randomized RHS In this section, we look into the computational power of the three different versions of P systems with randomized right-hand sides. We first shortly consider the case of cooperative rules and then focus on the case of non-cooperative rules. 26 A. Alhazov, R. Freund, S. Ivanov 4.1 Cooperative Rules The following result concerning the relationship between P systems with individual randomized RHS and conventional P systems holds for both cooperative and noncooperative rules: Proposition 2. For any n∈N+and α∈ {ncoo, coo},PsOPn(rndRhs, α)⊇ PsOPn(α). Proof. Any conventional P system can be trivially seen as a P system with individual randomized RHS in which every production has exactly one right-hand side.  Now, the computational completeness of cooperative P systems trivially implies the computational completeness of P systems with individual randomized RHS. Corollary 1. For any n∈N+,PsOPn(rndRhs, coo) = P sRE. 4.2 Non-cooperative Rules First we mention an upper bound for the families P sOPn(ρ, ncoo), for any variant ρ∈ {rhsExchange,rhsPools0,rndRhs}: Proposition 3. For any n∈N+and ρ∈ {rhsExchange,rhsPools0,rndRhs}, PsOPn(ρ, ncoo)⊆PsET0L. Proof. No matter how the rule sets are constructed in the three different variants, we always get a finite set of different sets of rules—tables—corresponding to tables in ET0L-systems, which can also mimic the contents of different membranes in the usual way by using symbols marked with the corresponding membrane label.  Next we show one of the central results of this paper: randomized rule righthand sides allow for generating non-semilinear languages already in the noncooperative case. Theorem 2. The following is true for ρ∈ {rhsExchange,rhsPools0,rndRhs}: {2m|m∈N} ∈ NOPn(ρ, ncoo)\NOPn(ncoo). Proof. The statement follows (for n≥1) from the constructions given in Examples 6, 7, and 8 and from the well-known fact that non-cooperative P systems operating under the total halting condition cannot generate non-semilinear number languages (for example, see [14]).  P Systems with Randomized Rules 27 This result is somewhat surprising at a first glance, but becomes less so when one remarks that the constructions from all three examples only effectively use one rule to do the multiplication, which is non-deterministically changed to a “halting” rule. Since there is only one rule acting at any time, randomized right-hand sides allow for clearly delimiting different derivation phases. It turns out that this approach of synchronization by randomization can be exploited to generate even more complex non-semilinear languages. Theorem 3. Given a fixed subset of natural factors {f1, . . . , fk} ⊆ N, the following is true for any ρ∈ {rhsExchange,rhsPools0,rndRhs}: L={fn1 1·. . . ·fnk k|n1, . . . , nk∈N} ∈ NOP1(ρ, ncoo). Proof. First consider the P system with randomized pools of RHS Π5= ({a, b},{b},[1]1, a, H, 1) with H= (l, r), l= (a) and r=af1. . . afkb. This P system is graphically represented in Figure 5. a af1 . . . afk b a1 Fig. 5. The P system Π5with randomized pools of RHS generating the number language {fn1 1·. . . ·fnk k|n1,...,nk∈N}. Similarly to the P systems from Examples 6, 7, and 8, Π5halts by choosing to pick the right-hand side band constructing the rule a→b. If Π5picks a different right-hand side, it will multiply the contents of the skin membrane (membrane 1) by one of the factors fi, 1 ≤i≤k. This proves that L∈NOP1(rhsPools0, ncoo), and, according to Theorem 1, L∈NOP1(rhsExchange, ncoo) as well: take the P system with the rules {a→af1, z2→af2, . . . , zk→afk, zk+1 →b}(the rules with zjin their left-hand sides are dummy rules). To show that L∈NOP1(rndRhs, ncoo), just construct a P system with the only production a→ {af1, . . . , afk, b}. Therefore, randomizing the right-hand sides of rules in non-cooperative P systems allows for generating non-semilinear languages which cannot be generated without randomization. A natural question to ask is whether randomizing the RHS leads to a strict increase in the computational power. The answer is trivially positive for P systems with individual randomized RHS (Variant 3). Proposition 4. For any n∈N+,PsOPn(rndRhs, ncoo))PsOPn(ncoo). 28 A. Alhazov, R. Freund, S. Ivanov Proof. The inclusion follows from Proposition 2, as any conventional P system can be trivially seen as a P system with individual randomized RHS in which every production has exactly one right-hand side. Theorem 3 proves the strictness of the inclusion.  On the other hand, the other two variants of randomizing right-hand sides— random RHS exchange (Variant 1) and randomized pools of RHS (Variant 2)— actually prevent one-membrane P systems with non-cooperative rules from generating some semilinear languages, which result also shows that flattening is not possible for these two variants. In what follows, we will use the expression “only one rule is applied” to refer to the fact that only one given rule u→vis applied in a certain configuration, possibly in multiple copies. Dually, by saying “at least two rules are applied”, we mean that at least two different rules, u→vand u0→v0, are applied, possibly in multiple copies each. Theorem 4. For ρ∈ {rhsExchange,rhsPools0}, the following holds: Lab ={an|n∈N}∪{bn|n∈N}/∈PsOP1(ρ, ncoo). Proof. Consider a P system Πwith randomized RHS of the variant given by ρ and with non-cooperative rules. We immediately remark that no left-hand side in Πmay be aor b, because in this case Πwill never be able to halt with its only (skin) membrane containing either the multiset anor bn. Furthermore, any RHS of Πcontains combinations of symbols a,b, or LHS symbols. Indeed, if an RHS contained a symbol not belonging to these three classes, instances of this symbol would pollute the halting configuration. Finally, Πcontains no RHS vsuch that a∈vand b∈v. If Πdid contain such an RHS, then any computation could be hijacked to produce a mixture of symbols aand b. With these remarks in mind, the statement of the theorem follows from the contradicting Lemmas 1 and 2, which are shown immediately after this proof.  Lemma 1. Take a Π∈OP1(ρ, ncoo),ρ∈ {rhsExchange,rhsPools0}, such that it generates the number language Ps(Π) = Lab. Then it must have a computation in which more than one rule is applied (two different left-hand sides are employed) in at least one step. Proof. Suppose that Πapplies exactly one rule in every step of every computation. We make the following two remarks: 1. Since the words in Lab are of unbounded length, Πmust have an LHS tand an RHS vsuch that t∈v, otherwise all computations of Πwould have one step and would only produce words of bounded length. 2. Every such RHS vmust contain at most one kind of LHS, i.e., if t1and t2are two LHS of Πthen t1∈vand t2∈vimplies t1=t2. If this were not the case, after using v,Πwould have to apply two different rules (assuming that Πhas at least as many RHS as LHS). P Systems with Randomized Rules 29 According to these observations, as well as to those from the proof of Theorem 4, any RHS vof Πis the of the form v=αβ, where α∈ {ak, bk|k∈N}, β∈ {tk|k∈N}, and tis an LHS of Π. Note that both αand βmay be empty. According to observation (1), Πmust have at least an RHS for which β6=λand there exists such an RHS which must be applied an unbounded number of times. In what follows, we will separately treat the cases in which Πcontains or does not contain mixed RHS, i.e., RHS for which both α6=λand β6=λ. No mixed RHS: Suppose that any RHS of Πwhich contains a left-hand side is of the form tk 2. Then, according to our previous observations on the possible forms of the RHS of Π, all RHS containing aare of the form aiand all RHS containing bare of the form bj. According to the remarks from the proof of Theorem 4, aand bmust not be LHS of Π. Therefore, in any computation of Π, all of a’s and b’s are produced in the last step. But then, the number of terminal symbols Πproduces in a computation can be calculated as a product of the sizes of the RHS of the rules it has applied, which implies that there exists such a p∈Nsuch that ap/∈P s(Π) and therefore Ps(Π)6=Lab. (pmay be picked to be the smallest prime number greater than the length of the longest RHS of Π.) Mixed RHS: It follows from the previous paragraph that, in order to generate the number language Lab,Πshould contain and apply at least one RHS of the form aitk1 1and at least one RHS of the form bjtk2 2. Take a computation Cof Πproducing aand applying the rule t→aitk1 1at a certain step. Instead of this rule, apply t→bjtk2 2, and, in the following step, the rule t2→aitk1 1. (We can do so because Πis allowed to pick any permutation of RHS.) Now, Πmay continue applying the same rules as in Cand eventually halt with a configuration containing both aand b. This implies that Ps(Π)6=Lab. It follows from our reasoning that, if Πapplies exactly one rule in any step of any computation, it cannot produce Lab, which proves the lemma.  Lemma 2. Take a Π∈OP1(ρ, ncoo),ρ∈ {rhsExchange,rhsPools0}, such that it generates the number language Ps(Π) = Lab. Then, in every computation of Π, exactly one rule is applied (one left-hand side is employed) in every step. Proof. Suppose that, in every computation of Π, there exists a step at which at least two different rules are applied. This immediately implies that Πhas no RHS of the form aior bj, for i, j ≥0. Indeed, consider a computation producing the multiset anand a step in it at which more than one rule is applied. Then Πcan replace one of the RHS introduced into the system at this step by bjand thus end up with a mix of a’s and b’s in the halting configuration. Therefore, all RHS of Πcontaining ahave the form aivaand all RHS containing bhave the form bjvb, 30 A. Alhazov, R. Freund, S. Ivanov where vaand vbare non-empty multisets which only contain LHS symbols (which are neither anor b). Now, consider a computation Caof Πhalting on the multiset an, and take the last step saat which at least two different rules are applied. We will consider three different cases, based on whether aand an LHS tappear in the configurations of Caafter step sa. Both aand tare present: Suppose both aand an LHS tare present at step sa+ 1 in computation Ca. Then tis the only LHS present, because, by our hypothesis, only one rule is applied (maybe in multiple instances) at step sa+ 1. In this case, replace the rule applied at step sa+ 1 in Caby t→bjvb, where bjvbis a right-hand side of Πused in a computation Cbproducing b’s. From step sa+ 2 on in the modified computation, just apply the same rules as applied to the symbols of vb(and to those derived from vb) in Cb. The modified computation will reach a halting configuration containing a mix of a’s and b’s. Only ais present: Suppose only ais present at step sa+ 1 in computation Ca. Then all of the RHS used at step saare λ, because Πhas no RHS of the form ai. Then, replace one of these empty RHS by bjvb, where bjvbis a right-hand side of Πused in a computation Cbproducing b’s. As before, just apply the same rules as in Cbin the modified computation to get a mix of a’s and b’s in the halting configuration. No symbols aare present: Suppose now that there are no instances of apresent at step sa+1 in computation Ca. Recall that Πhas no RHS of the form ai. Since we suppose that sais the last step at which at least two different rules are applied, this means that, in order to produce any a’s in Ca,Πmust have and use an RHS of the form aitk. This RHS contains (multiple copies of) exactly one kind of LHS symbol: t. Consider a computation Cbhalting on the multiset bn. We pick nsufficiently big to ensure that Cbuses at least two RHS containing b:bjvband bj0v0 b(possibly the same). Without losing generality, we may suppose that these two RHS are either used at the same step in Cbor that bj0v0 bis used at a later step than bjvb. Then, replace bj0v0 bby aitk, pick one of the LHS symbols t0∈v0 band apply the same rules to t(and to the symbols derived from t) in the modified derivation as were applied to t0(and to the symbols derived from t0) in Cb. The modified derivation will therefore contain a mix of a’s and b’s in the halting configuration. It follows from our reasoning that, if in any derivation of Πthere is a step at which at least two different rules are applied, then P s(Π)6=Lab, which proves the lemma.  P Systems with Randomized Rules 31 The previous two lemmas are contradicting each other, which means that there exist no one-membrane P systems with random RHS exchange or with random pools of RHS which generate the union language Lab ={an|n∈N}∪{bn|n∈N} (this is the statement of Theorem 4). Together with Theorem 3, this leads us to the curious conclusion that one-membrane non-cooperative P systems with random RHS exchange or with randomized pools of RHS are incomparable in power to the conventional P systems. Corollary 2. For ρ∈ {rhsExchange,rhsPools0}, the following two statements are true: PsOP1(ρ, ncoo)\PsOP1(ncoo)6=∅,(1) PsOP1(ncoo)\PsOP1(ρ, ncoo)6=∅.(2) Proof. Statement (1) follows from Theorem 3. Statement (2) follows from Theorem 4.  Theorem 4 also allows us to draw a negative conclusion as to the computational completeness of one-membrane non-cooperative P systems with random RHS exchange (Variant 1) and non-cooperative P systems with randomized pools of RHS (Variant 2). Corollary 3. For ρ∈ {rhsExchange,rhsPools0}, the following is true: PsOP1(ρ, ncoo)(PsRE. It turns out that allowing multiple membranes strictly increases the expressive power of Variants 1 and 2 and allows for easily generating all semilinear languages, as shown by the following theorem. Theorem 5. For ρ∈ {rhsExchange,rhsPools0}, the following holds: N∗SLINN∈P sOP∗(ρ, ncoo). Proof. Consider the following semilinear language of d-dimensional vectors L= S1≤i≤nhAi,biiN, where Ai⊂fin Ndand bi∈Nd. We construct the corresponding P system with randomised pools of RHS: Π6=O, T, [ [ ]2. . . [ ]n+1 ]1, w0, λ, . . . , λ, H1,...Hn+1,1, with the alphabet and the initial contents of the skin defined as follows: •O={a1, . . . , ad, t}contains a symbol per each dimension of the vectors, plus the special symbol t, •T={a1, . . . , ad}contains exactly one symbol per dimension of vectors, •w0=t. 38 A. Alhazov, R. Freund, S. Ivanov 6.1 Equivalence Between Variants 1 and 2 for Variant A For randomized pools of RHS, again we consider the restriction that there are at least as many right-hand sides as it has left-hand sides for the rules to be constructed, i.e., the type rhsPools0. Then again we obtain the equivalence between tissue P systems with random RHS exchange and tissue P systems with randomized pools of RHS of type rhsPools0. The proof follows the same lines as the proof of Theorem 1, now taking into account that we only have to consider the whole system (or, if rules are assigned to cells, we simply replace membrane by cell). Proposition 5. For any n∈N+and X∈ {coo, ncoo}, the following holds: PsOtPn(rhsExchange, X) = PsOtPn(rhsPools0, X). 7 Conclusions and Open Problems In this article, we introduced and partially studied P systems with randomized rule right-hand sides. This is a model of P systems with dynamic rules, in which the matching between left-hand and right-hand sides is non-deterministically changed during the evolution. In each step, such P systems first construct the rules from the available rule sides and then apply them, in a maximally parallel way. We defined three different randomization semantics: random RHS exchange (Variant 1), randomized pools of RHS (Variant 2), and individual randomized RHS (Variant 3). We studied the computational power of the three variants and showed that Variant 3 is quite different in power from Variants 1 and 2. Indeed, P systems with individual randomized RHS (Variant 3) appear as a strict extension of conventional P systems, while random RHS exchange (Variant 1) and randomized pools of RHS (Variant 2) seem to increase the power when only one LHS is used, but to decrease the power when more LHS are present. Finally, we gave a binary normal form for P systems with individual randomized RHS (Variant 3). 7.1 Open Questions The present work leaves open quite a number of open questions. We list the ones appearing important to us, in no particular order. Full power of Variants 1 and 2: Are cooperative, multi-membrane P systems with random RHS exchange (Variant 1) or with randomized pools of RHS (Variant 2) computationally complete? If not, what would be the upper bound on their power? In this article, we showed that applying these two randomization semantics to the non-cooperative, onemembrane case, yields a family of multiset languages incomparable with the family of semi-linear vector sets. How much more can be achieved with cooperativity? P Systems with Randomized Rules 39 We conjecture that, even with LHS containing more than one symbol, Variants 1 and 2 will not be computationally complete. However, we expect that considering systems with multiple membranes may actually bring a substantial boost in computational power, because, in both Variants 1 and 2, randomization happens over each single membrane, meaning that one might use a rich membrane structure to finely control its effects. Compare the variants: How do the three variants of RHS randomization compare among one another when applied to non-cooperative rules? We saw that, in all three cases, exponential number languages can be generated. We also saw that individual randomized RHS (Variant 3) produce a strict superset of the semi-linear languages (Proposition 4). Does it imply that Variant 3 is strictly more powerful than Variants 1 and 2? We conjecture a positive answer to this question. Excess of LHS: In the case of P systems with randomized pools of RHS (Variant 2), what is the consequence of having more LHS available in a membrane than there are RHS? The results in this paper concern a “restricted” version of Variant 2, in which we require that LHS are never in excess. How strong is this restriction? Our conjecture is that allowing an excess of LHS does not increase the computational power. Applications to vulnerable systems: As noted in the introduction to the present work, randomized RHS can be seen as a representation of systems mutating in a toxic environment. However, we did not give any concrete examples. It would be interesting to look up any such concrete cases and to evaluate the relevance of this unconventional modeling approach. 7.2 Further Variants Forbidding identical rules: In any of the three variants, it may happen that identical rules are constructed, in any membrane. In the previous chapters, in this case this rule was simply taken into the set of rules. Yet we could also forbid such a situation to happen and in such a case completely abandon the whole rule set. Another solution can be to take out all rules having been constructed more than once from the constructed rule set. The situation of getting identical rules can easily be avoided by avoiding identical RHS: the right-hand sides of rules can be made different by adding suitable powers of a dummy symbol d, which does not count for the final result (i.e., dis no terminal symbol). As dalso does not appear on the left-hand side of a rule, the computational power of any of the P systems variant considered in this paper will not be changed by this changing of the set of RHS available for constructing the set of rules. 40 A. Alhazov, R. Freund, S. Ivanov Identical RHS in Variant 3: In P systems with individual randomized RHS the computational power mainly arises from the possibility to specify different sets of RHS for the left-hand sides of rules. What happens if the set Rof RHS must be the same for all left-hand sides? References 1. Artiom Alhazov. A note on P systems with activators. In Gheorghe P˘aun, Agust´ın Riscos-N´u˜nez, Alvaro Romero-Jim´enez, and Fernando Sancho-Caparrini, editors, Second Brainstorming Week on Membrane Computing, Sevilla, Spain, February 2-7 2004, pages 16–19, 2004. 2. Artiom Alhazov, Rudolf Freund, Sergiu Ivanov, and Marion Oswald. Observations on P systems with states. In Marian Gheorghe, Ion Petre, Mario J. P´erez-Jim´enez, Grzegorz Rozenberg, and Arto Salomaa, editors, Multidisciplinary Creativity. Hommage to Gheorghe P˘aun on His 65th Birthday. Spandugino, 2015. 3. Artiom Alhazov, Sergiu Ivanov, and Yurii Rogozhin. Polymorphic P systems. In Marian Gheorghe, Thomas Hinze, Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, editors, Membrane Computing, volume 6501 of Lecture Notes in Computer Science, pages 81–94. Springer, 2011. 4. Fernando Arroyo, Angel V. Baranda, Juan Castellanos, and Gheorghe P˘aun. Membrane computing: The power of (rule) creation. Journal of Universal Computer Science, 8:369–381, 2002. 5. Ilir C¸ apuni and P´eter G´acs. A Turing machine resisting isolated bursts of faults. CoRR, abs/1203.1335, 2012. 6. Matteo Cavaliere and Daniela Genova. P systems with symport/antiport of rules. In Gheorghe P˘aun, Agust´ın Riscos-N´u˜nez, Alvaro Romero-Jim´enez, and Fernando Sancho-Caparrini, editors, Second Brainstorming Week on Membrane Computing, Sevilla, Spain, February 2–7 2004, pages 102–116, 2004. 7. Matteo Cavaliere, Mihai Ionescu, and Tseren-Onolt Ishdorj. Inhibiting/de-inhibiting rules in P systems. In Pre-proceedings of the Fifth Workshop on Membrane Computing (WMC5), Milano, Italy, June 2004, pages 174–183, 2004. 8. Rudolf Freund. Generalized P-Systems. In Gabriel Ciobanu and Gheorghe P˘aun, editors, Fundamentals of Computation Theory, 12th International Symposium, FCT ’99, Ia¸si, Romania, August 30–September 3,1999, Proceedings, volume 1684 of Lecture Notes in Computer Science, pages 281–292. Springer, 1999. 9. Rudolf Freund. P systems working in the sequential mode on arrays and strings. In Cristian Calude, Elena Calude, and Michael J. Dinneen, editors, Developments in Language Theory, 8th International Conference, DLT 2004, Auckland, New Zealand, December 13-17, 2004, Proceedings, volume 3340 of Lecture Notes in Computer Science, pages 188–199. Springer, 2004. 10. Rudolf Freund, Alberto Leporati, Giancarlo Mauri, Antonio E. Porreca, Sergey Verlan, and Zandron. Flattening in (tissue) P systems. In Artiom Alhazov, Svetlana Cojocaru, Marian Gheorghe, Yurii Rogozhin, Grzegorz Rozenberg, and Arto Salomaa, editors, Membrane Computing, volume 8340 of Lecture Notes in Computer Science, pages 173–188. Springer, 2014. P Systems with Randomized Rules 41 11. Rudolf Freund and Sergey Verlan. A formal framework for static (tissue) p systems. In George Eleftherakis, Petros Kefalas, Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, editors, Membrane Computing: 8th International Workshop, WMC 2007 Thessaloniki, Greece, June 25-28, 2007. Revised Selected and Invited Papers, pages 271–284. Springer, 2007. 12. Sergiu Ivanov. Polymorphic P systems with non-cooperative rules and no ingredients. In Marian Gheorghe, Grzegorz Rozenberg, Arto Salomaa, Petr Sos´ık, and Claudio Zandron, editors, Membrane Computing - 15th International Conference, CMC 2014, Prague, Czech Republic, August 20–22, 2014, Revised Selected Papers, volume 8961 of Lecture Notes in Computer Science, pages 258–273. Springer, 2014. 13. Gheorghe P˘aun. Computing with Membranes. Journal of Computer and System Sciences, 61:108–143, 1998. 14. Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA, 2010. 15. Grzegorz Rozenberg and Arto Salomaa, editors. Handbook of Formal Languages, 3 volumes. Springer, New York, NY, USA, 1997. 16. Bulletin of the International Membrane Computing Society (IMCS). http:// membranecomputing.net/IMCSBulletin/index.php. 17. The P Systems Website. http://ppage.psystems.eu/. Time-freeness and Clock-freeness and Related Concepts in P Systems ? Artiom Alhazov1,2??, Rudolf Freund3, Sergiu Ivanov4,5, Linqiang Pan2,6, and Bosheng Song2 1Institute of Mathematics and Computer Science Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au, MD-2028, Moldova [email protected] 2Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China 3Faculty of Informatics, TU Wien Favoritenstraße 9–11, 1040 Vienna, Austria [email protected] 4LACL, Universit´e Paris Est – Cr´eteil Val de Marne 61, av. G´en´eral de Gaulle, 94010, Cr´eteil, France [email protected] 5TIMC-IMAG/DyCTiM, Faculty of Medicine of Grenoble, 5 avenue du Grand Sablon, 38700, La Tronche, France [email protected] 6School of Electric and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China Summary. In the majority of models of P systems, rules are applied at the ticks of a global clock and their products are introduced into the system for the following step. In timed P systems, different integer durations are statically assigned to rules; time-free P systems are P systems yielding the same languages independently of these durations. In clock-free P systems, durations are real and are assigned to individual rule applications; ?The work is supported by National Natural Science Foundation of China (61320106005 and 61033003) and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012). This paper was finished with Rudolf Freund during Artiom Alhazov’s and Sergiu Ivanov’s stay in Vienna in August 2017. ?? The work is supported by National Natural Science Foundation of China (61320106005 and 61033003) and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012). 44 A. Alhazov et al. thus, different applications of the same rule may last for a different amount of time. In this paper, we formalise timed, time-free, and clock-free P system within a framework for generalised parallel rewriting. We then explore the relationship between these variants of semantics. We show that clock-free P systems cannot efficiently solve intractable problems. Moreover, we consider un-timed systems where we collect the results using arbitrary timing functions as well as un-clocked P systems where we take the union over all possible per-instance rule durations. Finally, we also introduce and study mode-free P systems, whose results do not depend on the choice of a mode within a fixed family of modes, and compare mode-freeness with clock-freeness. 1 Introduction Membrane systems with symbol-objects are formal computational models of distributed multiset rewriting. While standard models often assume maximal parallelism and a global-clock synchronization of rules (overview in [12]), there have been a number of attempts in the literature to relax this condition. The extreme variant are so-called asynchronous systems, where the parallelism is arbitrary instead of maximal [1, 7]. Not surprisingly, in many cases such systems are much weaker (e.g., defining P sMAT instead of P sRE) or need much stronger ingredients to be able to perform the same goal. A different way to relax the global synchronisation condition is lifting the assumption that all rule executions take one step. For example, in timed P systems [5], a numerical function is defined, associating to each rule the positive integer number of steps its application takes. In this context, time-freeness is an (undecidable) property that the result of all computations of a P system does not depend on the timing function. The motivation for studying time-freeness is investigating the power and the efficiency of P systems that are robust with respect to rule execution times. Yet, the definition of the time-freeness property is not restrictive enough for some goals— the time a rule application lasts cannot be different in different situations. Indeed, since the timing function is defined on the set of rules, the following facts are immediate: 1. If a rule is simultaneously applied multiple times, then all instances finish simultaneously. 2. If a rule is simultaneously applied in different membranes with the same label, then all rules finish simultaneously. 3. If a rule is applied at different steps of a computation, then all instances last for the same amount of time. 4. If a rule is applied in different non-deterministic branches of a computation, then all instances last for the same amount of time. A number of publications investigate the efficiency of time-free P systems in solving intractable problems, e.g. [15, 16, 17, 18]. We believe that the constructions in these publications rely on the residual synchronisation facts listed above. Time-freeness and Clock-freeness in P Systems 45 In this paper we focus on a variant of timing which allows individual rule executions to last differently. This variant was introduced under the name “clockfreeness” in [14]. In clock-free P systems, rule applications may last for “arbitrary” real periods and even applications of the same rule may have different durations. We prove that clock-freeness deprives any variant of P systems operating under this semantics of the capability of solving intractable (NP-complete) problems in polynomial time. Clock-freeness changes the way in which a P system operates quite a bit. Indeed, since durations of rule applications are real numbers, such a P system does not follow the ticks of a global clock any more, but instead “listens” to events— situations in which rule applications finish and release new potential reactants (compare this to the preliminary observations in [11]). Such a P system therefore becomes event-driven and operates in continuous time, similarly to the Gillespie algorithm [10] or to data stream-driven reactive programs, e.g. [6]. In the present work, we formally define event-driven P systems and show their relationship to clock-free and time-free P systems. Moreover, we also introduce un-timed and unclocked P systems, where as a result we take the union of all results obtained by any timing and per-instance timing function, respectively. We also consider yet another freeness property: mode-freeness. A P system which is mode-free with respect to a family of modes has the same behaviour under all modes from this family. We show a large family of modes under which generating P systems yield trivial languages, but accepting P systems are computationally complete. Finally, we explore the form of some clock-free and mode-free P systems and show some relatively strong connections between the two freeness properties. This article is organised as follows. Section 2 recalls some basic notions of formal language theory and then introduces a general definition of P systems rewriting objects from a computable set O. Section 3 recalls and formally defines timing functions, time- and clock-free P systems, as well as introduces event-driven P systems. Subsection 3.4 investigates the connections between these objects. Section 4 shows one of the main results of this paper: clock-free P systems cannot solve intractable problems in polynomial time. Section 5 introduces un-timed and un-clocked P systems. Section 6 recalls the notion of an evolution mode, introduces mode-freeness with respect to a family of modes, and then shows some properties of mode-free P systems. Section 7 compares clock-freeness with mode-freeness and points out some connections between these two properties. Section 8 discusses further possibilities for defining per-instance timing and clock-freeness. Section 9 concludes the paper and also lists several open problems. 2 Preliminaries We assume the reader to be familiar with the basics of formal language theory and P systems, but we recall some of the notions for convenience. For further 46 A. Alhazov et al. introduction to the theory of formal languages and P systems, we refer the reader to [12, 13]. After recalling these basic notions, we will give a formal explanation of general rewriting in order to be able to introduce a general definition of P systems as hierarchical rewriting systems, somewhat in the spirit of [2] and [8]. 2.1 Multisets Amultiset over Vis any function w:V→N;w(a) is the multiplicity of ain w. A multiset wis often represented by one of the strings containing exactly w(a) copies of each symbol a∈V. The set of all multisets over the alphabet Vis denoted by V◦. By abusing string notation, the empty multiset is denoted by λ. We will also (ab)use the symbol ∈to denote the relation “is a member of” for multisets. Therefore, for a multiset w,a∈wwill stand for w(a)>0. Given two multisets w, v ∈V◦,wis a submultiset of vif w(a)≤v(a), for all a∈V. In this case, removing wfrom vmeans constructing the multiset v−w with the property (v−w)(a) = v(a)−w(a). For a multiset of tuples w∈(A1×. . . ×An)◦we will use the notation w|Ai to refer to the multiset of projections of the elements of won the dimension Ai, 1≤i≤n. Formally, w|Ai∈A◦ iand w(ai) for a fixed ai∈Aiis equal to the number of tuples of the form (a1, . . . , ai, . . . , an) in w. 2.2 General Sequential and Parallel Rewriting Consider an (infinite, computable) alphabet of objects O. An O-rewriting rule is a partial function r:O→O. For an object o∈Ofor which r(o) is undefined, we say that ris not applicable to o. Often, the semantics of computing r(o) is given by “removing the left-hand side” or rfrom the object oand then “adding back the right-hand side”. Accordingly, we define the pair of partial functions r−, r+:O→Osuch that their total effect is the same as that of r, i.e., r=r+◦r−. Example 1. Consider the alphabet V={a, b}and the set O=V◦of all finite multisets over V. The partial function r:V◦→V◦replacing an instance of a with two instances of bis an O-rewriting rule and is often written as r:a→bb or r:a→b2(note that, in this notation, the symbol →is used to specify rule sides and not the domain or the codomain of a function); ris defined for all multisets containing at least an instance of aand is undefined for all other multisets. For the multiset rewriting rule r, the value r−(w) can be defined by removing the left-hand side afrom the multiset w(if possible) and r+(w) by adding the right-hand side bb to w. Thus, r=r+◦r−. Example 2. Consider, again, the alphabet V={a, b}and the set O=V∗of all finite strings over V. In this case, an O-rewriting rule is a partial function r:O→Oreplacing a substring at a particular position. To express the effect of rewriting any substring of a string s∈Osatisfying some particular criteria, we Time-freeness and Clock-freeness in P Systems 47 need to consider a family of functions (ri:O→O)i∈Ireplacing the substring at its i-th occurrence. To express the effect of rewriting any substring in any finite string in O, we need to consider the family of functions (ri:O→O)i∈N. Fix a set of O-rewriting rules R. To capture the possibility of applying multiple rules Rin parallel, we define the (computable) partial function apply :R◦×O→O which applies a multiset of rules from Rto an object from Oand yields a new object in O, if possible. As for the case of individual rules, to represent the idea of “removing the left-hand sides” and “adding the right hand sides”, we define two other mappings apply−and apply+such that apply(ρ, o) = apply+(ρ, apply−(ρ, o)), with ρ∈R◦and o∈O. Example 3. Consider the alphabet V={a, b}and O=V◦, as in Example 1, and two rewriting rules r1:ab →bb as well as r2:bb →a. Take the multiset of rules ρ=r1r2; classically, the function apply(ρ, w) is defined for such multisets w∈Owhich contain the submultiset ab3=ab bb, necessary to satisfy both the applicability requirements of rules r1and r2. In this case, apply−(ρ, w) is the function removing the multiset ab3from w,apply+(ρ, w) is the function adding bb a to w, and apply(ρ, w) is the function first removing ab3from wand then adding bb a. Asequential O-rewriting framework is the pair (O, R), where Ois a set of objects and Ris a set of R-rewriting rules. A parallel O-rewriting framework is the pair (O, R, apply−, apply+), where (O, R) is a sequential O-rewriting framework and apply−, apply+:R◦×O→Oare the (computable) partial functions defining the semantics of parallel application of rules from Rto objects in O. Our definition of rewriting frameworks are strongly inspired by the work [8]. 2.3 P Systems The definition of P systems we give in this paper directly generalises various models of cell-like (hierarchical) P systems in which rules are “located within” the membranes and whose membrane structure may evolve: transition P systems with membrane dissolution rules, P systems with active membranes, etc. A comprehensive overview of different flavors of membrane systems and their expressive power is given in the handbook which appeared in 2010, see [12]. For a state of the art snapshot of the domain, we refer the reader to the P systems website [20], as well as to the bulletin of the International Membrane Computing Society [19]. Given a parallel O-rewriting framework (O, R, apply−, apply+), a P system is the following tuple: Π= (O, OT, µ, w1, . . . , wn, I, R1, . . . , Rn, hi, ho), where Ois a (computable, infinite) set of objects, OT⊆Ois a (computable) set of terminal objects, µis the initial membrane structure injectively labelled by 54 A. Alhazov et al. 1. Apply the finishing function to find the submultiset of rules ρnow which must finish: ρnow =φ(γ, ρi). Take the multiset ρnow|Rof all rewriting rules in ρnow and compute the new object w0 i=apply+(ρnow|R, wi); also implement the effect of the ingredients listed in ρnow. Build ρ0 iby removing ρnow from ρi. 2. Pick a multiset of rules ρapp applicable to w0 iaccording to a fixed evolution mode and add ρapp to ρ0 i, thereby constituting the new rule queue ρ00 i. Compute the new object w00 iin the following way: w00 i=apply−(ρapp, w0 i). 3. In configuration Cj+1, set the contents of membrane ito w00 iand its rule queue to ρ00 i. As before (Subsections 3.1 and 3.2), all computations start with empty rule queues and the system needs to exhaust all rule queues in order to halt. The result is retrieved as for P systems operating under conventional semantics (Subsection 2.3). Recall that the finishing function φis allowed to return an empty multiset. In this paper, we choose to only consider functions which, for a given sequence of configurations γof a fixed P system Π, return a non-empty multiset for at least one rule queue (non-denying functions). This ensures that every configuration in a computation of Πcorresponds to a rule finishing event. Example 6. Consider again the P system from Example 4: Π1= ({a, b}◦,{a, b}◦,[ ]1, a, {none},{r1:a→bb, r2:b→aa},1,1) and the first three configurations of its computation (C0, C1, C2) illustrated in Figure 1. We can reproduce the effects of these three steps using a finishing function. The initial configuration will be, as before, K0= ([ ]1, aa, λ). In this configuration the maximally parallel mode forces Πto apply r1twice and to move into the following configuration K1= ([ ]1, λ, (r1, none)2). We define the finishing function φto return (r1, none) for history (K0, K1) and the queue (r1, none). This will release the products of r1into the skin membrane and render r2applicable. The maximally parallel derivation mode enforces the two applications of r2, moving Π1into the configuration K2= ([ ]1, λ, (r1, none) (r2, none)2). We now show side by side the configurations C0,C1, and C2of Π(τ) working under the per-instance real timing function τfrom Example 4 and the configurations K0,K1, and K2from the previous example (we denote t1= 0.5 + sin 1 and t2= 0.5 + cos 1): Note that, with the finishing function from Example 6, we are able to reproduce the contents of rule queues in (C0, C1, C2), without using time stamps. We will later formally show that per-instance real timing functions are equivalent to finishing functions, which makes them into a useful instrument for reasoning about computations with per-instance real timing. For a P system Πto be independent of the finishing strategy φmeans that there exists a language L⊆Oof objects of Πsuch that L=Π(φ) for any computable finishing function φ. Time-freeness and Clock-freeness in P Systems 55 CiKi 0 ([ ]1, aa, λ) ([ ]1, aa, λ) 1 ([ ]1, λ, (r1, none, 0.5) (r1, none, √2)) ([ ]1, λ, (r1, none)2) 2 ([ ]1, λ, (r1, none, √2) (r2, none, t1) (r2, none, t2)) ([ ]1, λ, (r1, none) (r2, none)2) Table 1. A comparison between the forms of configurations in Examples 4 and 6. We denote t1= 0.5 + sin 1 and t2= 0.5 + cos 1. Since a finishing function essentially defines the sequencing of the releases of “processed” rule products, P systems which are independent of this sequencing can be seen as “waiting” for events to happen and “handling” them. Thus, we will refer to such systems using the term event-driven P systems. Finally, in analogy with Markovian per-instance timing functions, we define Markovian finishing strategies. We will call a strategy φa Markovian finishing strategy if its value does not depend on the first argument. Formally, φis Markovian if, for a fixed multiset of rules ρand for any two sequences of configurations γ1 and γ2, the following holds: τ(γ1, ρ) = τ(γ2, ρ). We will call P systems which are event-driven with respect the class of Markovian finishing functions Markovian event-driven. 3.4 Timing Types and Finishing Strategies Because timed P systems, P systems with per-instance real timing, and P systems with finishing strategies stem from the same idea—introduce rule durations to P systems—it is not surprising that these models have a lot in common. In this subsection, we outline the main connections. First of all, we would like to bring the reader’s attention upon the form of the configurations shown in Table 1: in many of them, the multisets contained in the membranes are empty, the “semantic focus” being on rule queues. This is an effect which may be surprising at first, but which actually underlines the important difference of P systems with rule queues as compared to usual P systems: in the former case, configurations mark the intervals the start of some rule applications and the end of some other rule applications (also seen in Figure 1), while configurations for P systems operating under conventional semantics (Subsection 2.3) capture the moments between the end of some rule applications and the start of some other rule applications. We will now show a series of intuitively clear inclusions of families of P systems with rule queues. We start with a general statement about timing functions and per-instance real timing functions. Proposition 1. Given a P system Πand any timing function e(Subsection 3.1) there exists a per-instance real timing function τe(Subsection 3.2) such that L(Π(e)) = L(Π(τe)). 56 A. Alhazov et al. Proof. Consider the timing function τealways assigning the duration e(r) to any application of the rule rin any evolution of Π. It follows from the definitions of semantics in Subsections 3.1 and 3.2 that, for any computation γeof Π(e) there exists a computation γτof Π(τe) producing the same output object, and conversely. Moreover, for a given step j, the configurations Cj∈γeand Kj∈γτ are identical (modulo the inclusion of Ninto R). The converse proposition is not true: there exist per-instance timing functions which do not have a corresponding timing function. Proposition 2. There exists a multiset-rewriting P system Πand a per-instance timing function τsuch that L(Π(τ)) 6=L(Π(e)) for any timing function e. Proof (Sketch). Consider the one-membrane multiset rewriting P system Πwith the following rules: r1:a→c r3:cb →d r2:c→f r4:cd → ♥ Fix the starting multiset in the only membrane of Πto aab. We can construct a per-instance real timing function for Πwhich will yield the evolution shown in Figure 2. Note that the two applications of r1take a different amount of time, aab c c r1 r1 d r3 ♥ r4 Fig. 2. A computation impossible without per-instance timing (because two applications of r1:a→ctake different time). which lets the first carrive (on the right) to produce a dtogether with bso that, when the second carrives (on the left), it can produce ♥together with d. On the other hand, if all applications of r1lasted for the same amount of time, both c’s would appear at the same time, and one of them would have to evolve by rule r3 turning into fand guaranteeing that rule r4cannot be applied. The fact that in timed P systems in the sense of Subsection 3.1 different applications of the same rule last for the same amount of time implies the statement of the proposition. According to the previous two propositions, per-instance timing allows richer behaviour than simple timing (in the sense of Subsection 3.1). This immediately implies the following statement. Time-freeness and Clock-freeness in P Systems 57 Theorem 1. A P system Πwhich is clock-free is also time-free. The relationship between per-instance timing functions and finishing strategies is even stronger. In the following, we say that two rule queues are equivalent modulo timestamps removing all timestamps from both yields two equal rule queues. We also consider the natural extension of this equivalence to configurations with rule queues. Proposition 3. Given an O-rewriting P system Πand any per-instance real timing function τsuch that its value τ(α, o)for the object o∈Odoes not depend on the timestamps in the sequence of configurations α, there exists a finishing strategy φsuch that L(Π(τ)) = L(Π(φ)). Proof. Take a computation γof Π(τ) and suppose that we have already defined φsufficiently to build a prefix ¯γ0 jof length jof a computation γ0of Π(φ) in which all configurations are equivalent modulo timestamps to the corresponding configurations in the prefix ¯γjof γ. Extend the definition of φto require the same rules to finish in configuration Kjof γ0as those which are scheduled to finish in Cjin γ. Since we require τto be independent of the timestamps in ¯γj, extending φin this way is always possible. This observation, together with the fact that the starting configurations of γand γ0are vacuously equivalent modulo timestamps (since their rule queues are empty), implies that we can define φsuch that all configurations in γ0are equivalent modulo timestamps to the corresponding configurations in γ. This means that the results in the halting configurations of γ and γ0are equal, which proves the proposition. Corollary 1. Given a P system Πand any Markovian per-instance real timing function τ, there exists a finishing strategy φsuch that L(Π(τ)) = L(Π(φ)). This corollary directly implies the following statement about event-driven P systems and Markovian clock-free P systems. Theorem 2. Any P system Πwhich is event-driven is Markovian clock-free. The converse of Proposition 3 also holds. Proposition 4. Given a P system Πand any finishing strategy φ, there exists a per-instance real timing function τsuch that L(Π(φ)) = L(Π(τ)). Proof. Take a computation γof Π(φ); γis a sequence of configurations with simple rule queues (without timestamps). Construct a new sequence of configurations γ0 with R+-timed rule queues in which all rules in all rule queues of configuration Cj get the timestamp j. Now consider the per-instance real timing function τwhich assigns exactly these timestamps to rule applications in γ0. The fact that we can always carry out this transformation implies the statement of the proposition. 58 A. Alhazov et al. According to the previous proposition, per-instance timing strategies may ensure richer behaviour than finishing strategies, which implies the following statement. Theorem 3. A P system Πwhich is clock-free is event-driven (in the sense of Subsection 3.3). Figure 3 summarises the relations between the various kinds of freeness properties of P systems with rule queues we have considered in this paper. This figure Clock-free P systems Time-free P systems Event-driven P systems Markovian clock-free P systems Theorem 1 Theorem 2 Theorem 3 Fig. 3. Inclusions between the different kinds of freeness properties considered in this section. also takes into consideration that any clock-free P system is trivially Markovian clock-free (because Markovian per-instance timing functions form a proper subclass of per-instance timing functions). This relation is represented as a dashed arrow. 4 Clock-freeness and Efficiency: Pversus NP One of the famous features of some variants of P systems is the capability of solving intractable (NP-complete) problems in polynomial time. The classical approach is generating an exponential number of computing units in polynomial time, which allows fast exploration of the space of candidate solutions (see [12] for some classic examples). Recently, efficient time-free solutions to intractable problems have been provided, e.g. in [15, 16, 17, 18]. Since there is no upper bound on the values the timing function may assign, the authors of the cited papers measure the time complexity of their constructions in terms of rule starting steps—the number of moments in the evolution of the P system at which rule executions start—rather than in terms of the total running time. On the other hand, we tend to see the number of rule finishing steps as a better measure for time complexity of time- and clock-free P systems. We take as a motivating example a computation in which rules only start in the first configuration and then finish at different times. This computation has only one starting step, but Time-freeness and Clock-freeness in P Systems 59 it may have multiple finishing steps, the number of which is more closely related to the number of events that occurred. We now show that, assuming that in order to solve an NP-complete problem an exponential number of computing units is necessary, efficient (in terms of the number of finishing steps) clock-free solutions are impossible to construct (we assume P6=NP). The intuition is as follows: in time-free P systems, we may not assume any particular duration for a given rule application, but we are sure that all applications of the same rule take the same amount of time. The fact that this property is no longer guaranteed under clock-freeness turns out to be essential for (in)efficiency. Theorem 4. Consider an NP-complete problem Pand take a P system Πsolving it. Then there exists a per-instance (real) timing function under which all computations of Πcontain an exponential (in the size of the input) number of rule finishing steps (assuming that in order to solve an NP-complete problem an exponential number of computing units is needed). Proof. In P systems as defined in Subsection 2.3, the atomic “computing units” are single rule applications. Therefore, according to our assumption, Πmust run an exponential number of rule applications. Since Πoperates under per-instance timing, we can ensure that no two rule applications end at the same time, which implies that Πhas exponentially many rule finishing steps. 5 Un-timed and Un-clocked P Systems In contrast to time-free P systems, where all timing functions have to generate the same results, in an un-timed P systems we collect all the results obtained by using any timing function, i.e., for a given P system Πwe define Lun−timed(Π) = [ ttiming function L(Π, t). Moreover, in the same way, in an un-timed P system we collect all the results obtained by using any per-instance timing function, i.e., for a given P system Π we define Lun−clocked(Π) = [ τper−instance timing function L(Π, τ). In an un-clocked P system, we simply may assume each rule application to last an arbitrary amount of time. In the following we give a small example which yields different results when considered as an un-clocked or as an un-timed system and is neither time- nor clock-free: Example 7. We consider the one-membrane multiset rewriting P system Πwith the following non-cooperative rules with inhibitors: 60 A. Alhazov et al. r1:a→aa|¬cand r2: b →c Starting from the axiom ab, in parallel we have to apply both r1:a→aa|¬cand b→cin parallel. Considering Πas an un-timed system, r1can be applied again and again in parallel to all symbols abeing generated until the application of the rule r2has finished which immediately stops the derivation by the appearance of the inhibitor c. In sum, we obtain Lun−timed(Π) = [ ttiming function L(Π, t) = [ n∈N{a2nc}. Of course, this system is neither time- nor clock-free. The infinite set is generated not due to the choice between applicable rule multisets, but due to the non-deterministic choice of the timing function. Considering Πas an un-clocked system, again r1:a→aa|¬cand b→chave to be applied in parallel in the first step, and r1can be applied until the application of the rule r2has finished which immediately stops the derivation by the appearance of the inhibitor c. Yet in contrast to the un-timed version, the applications of the rule r1to the symbols aappearing in the meantime may end at arbitrary moments of time. To the two symbols aappearing when the first application of rule r1has finished, r1has to be applied simultaneously to both symbols a, yet from that moment on the different instances of rule r1may finish in an unsynchronized way. Hence, as we sum up all possible results, we may restrict ourselves to consider only the events when just one rule application ends. The only symbols to which a rule, i.e., r1, now can be applied are the two symbols ahaving evolved as a result of this one rule application, and to these two symbols two copies of r1have to be applied simultaneously. In fact, this only means that the number of symbols ahas increased by one with each finishing of a rule r1. Therefore, in sum we obtain Lun−clocked(Π) = [ τper−instance timing function L(Π, τ) = {anc|n∈N+\{1,3}}. A similar result can be obtained by the one-membrane multiset rewriting P system Π0with the following non-cooperative rules with promoters: r1:a→aa|b, r2:b→b, and r3: b →c Starting from the axiom ab, we now may assume that the execution of the rules r1and r2takes exactly the same time, because the promoter bis needed to allow the copies of rules r1to be applied. Again, the derivation halts as soon as the promoter bis eliminated by applying r3. For the un-timed mode, the application of rules r1still is synchronized, too, and we therefore obtain Lun−timed(Π0) = [ ttiming function L(Π0, t) = [ n∈N{a2nc}. Time-freeness and Clock-freeness in P Systems 61 In the un-clocked mode, the finishing of rules may be arbitrary, yet still the promoter bis needed to continue with applying rule r1, i.e., only when the application of the rule r2:b→bhas finished, rule r1can be applied. In sum, we again obtain Lun−clocked(Π0) = [ τper−instance timing function L(Π0, τ) = {anc|n∈N+\{1,3}}. 6 Mode-freeness Considering time-free, clock-free, and event-driven P systems motivates further discussion about robustness with respect to variations of other parameters. In this section we will consider mode-freeness: robustness with respect to the choice of the evolution mode. 6.1 Evolution Modes Take a (computable) set of objects Oand consider a parallel O-rewriting framework (O, R, apply−, apply+). Following [9], we denote by Appl(R, o) the set of multisets of rules applicable to the object o∈Oin parallel. Given an n-membrane O- rewriting P system Πand a configuration Cof it, we denote by Appl(Π, C) the set of tuples of the form (ρ1, . . . , ρn), in which ρiis a multiset of rules applicable to the object wiin membrane iin configuration C. Example 8. Consider the multiset ab and the set of multiset rewriting rules R={r1:a→b, r2:b→c}. Then Appl(R, ab) = {r1, r2, r1r2}. Take a multiset-rewriting P system Πwith the set of ingredients I={none}and two membranes with equal sets of rules R1=R2={(r1, none),(r2, none)}. Consider the configuration C= (µ, ab, ab) of Π, then Appl(Π, C) = A×A, where A={(r1, none),(r2, none),(r1, none)(r2, none)}. Given a P system Πand a configuration C, an evolution mode (derivation mode) is a strategy ϑfor filtering the set Appl(Π, C). According to [9], we denote by Appl(Π, C, ϑ)⊆Appl(Π, C) the set of tuples of multisets of rules of Πapplicable in configuration Caccording to the derivation mode ϑ. When Appl(Π, C, ϑ) contains more than one element, Πchooses between the allowed tuples nondeterministically in order to continue the computation. We will denote the language generated (respectively, accepted) by Πoperating under the derivation mode ϑby Lgen(Π, ϑ) (respectively, Lacc(Π, ϑ)). We will now recall some typical examples of derivation modes considered in [9]. All of these examples are formulated for a P system Πand a configuration Cof it. Example 9. The asynchronous derivation mode asyn is the mode allowing any combination of rules to be applied: Appl(Π, C, asyn) = Appl(Π, C). 62 A. Alhazov et al. Example 10. The sequential derivation mode sequ is the mode only allowing one rule to be applied at any time. Appl(Π, C, sequ) therefore contains tuples of singleton multisets of rules. Example 11. The maximally parallel derivation mode max only includes tuples of non-extendable multisets of rules. Formally, for a tuple (ρ1, . . . , ρn)∈Appl(Π, C, max), the set Appl(Π, C) contains no tuple (ρ0 1, . . . , ρ0 n) such that at least one ρiis a submultiset of ρ0 i, for 1≤i≤n. A very interesting derivation mode (considered in a detailed way in [3]) is the following one. Example 12. The set-maximally parallel mode smax only allows tuples of multisets containing at most one instance of any rule. Formally, for any tuple (ρ1, . . . , ρn)∈ Appl(Π, C, smax), it is true that ρi(r)≤1 for any rule rin membrane i, 1 ≤i≤n. Finally, we show several more derivation modes which we use later. Example 13. The max≥kmode only allows tuples of multisets which contain at least krules. That is, for any tuple (ρ1, . . . , ρn)∈Appl(Π, C, max≥k), it must hold that |ρi| ≥ k, for all 1 ≤i≤k. Example 14. Suppose that the sets of rules Riassociated with membranes iof Π, 1≤i≤n, are equipped with total orders ≤iand consider the mode det (“the determinator”) which only allows tuples of singleton multisets of rules, which are also minimal with respect to the corresponding order. Formally, for any tuple (ρ1, . . . , ρn)∈Appl(Π, C, det), it is true that |ρi| ≤ 1 and, for any other tuple of singleton multisets (ρ0 1, . . . , ρ0 n)∈Appl(Π, C), it holds that ri≤ir0 i, where ρi=ri, ρ0 i=r0 i, and 1 ≤i≤n. Note that, according to this definition, Appl(Π, C, det) is either empty (if Appl(Π, C) is empty) or a singleton set, which justifies the informal name “the determinator”. Finally, an extreme example of an evolution mode. Example 15. The empty evolution mode ∅is the evolution mode disallowing any rule applications: Appl(Π, C, ∅) = ∅. 6.2 Freeness with Respect to a Family of Modes Consider an O-rewriting P system Πand the family of evolution modes Θ. We say that Πis Θ-mode-free if there exists a language L⊆Osuch that L=L(Π, ϑ), for all ϑ∈Θ. We use the notation pLgen(O, Θ) to refer to the family of languages over Ogenerated by Θ-mode-free O-rewriting P systems. We replace the subscript gen by acc to refer to the family of languages accepted by Θ-mode-free O-rewriting P systems. Time-freeness and Clock-freeness in P Systems 63 It turns out that the idea mode-freeness has already been indirectly invoked in the literature. Indeed, the constructions from the paper [3] that literally hold for the modes max and smax are {max, smax}-mode free. We start our discussion of more general kinds of mode-freeness by remarking that mode-freeness with respect to the family of all modes (denoted by ΘU) is a very restrictive condition filtering out non-trivial behaviour. Proposition 5. Consider the family of all derivation modes ΘU. Then the following statements hold: •pLgen(O, ΘU)only contains ∅and singleton languages, •pLacc(O, ΘU) = 2O, where 2Ois the set of all subsets of O, but all computation is done by the procedure extracting the result from the output object. Proof. Consider the ΘU-mode free O-rewriting P system Π. Since Πshould yield the same language under any mode, it is sufficient to investigate its behaviour under the empty mode ∅. Under this mode, Πnever evolves. For generation, this means that the result is computed from the initial object placed in the output membrane, which, depending on the procedure for extracting the result, may yield a singleton language or the empty language (e.g., in the case in which the initial object in the output membrane has no corresponding terminal projection). Suppose now that Πis an acceptor. We will consider the following cases. •If Πaccepts by halting, it accepts any object because it halts immediately: Lacc(Π) = O. •Suppose Πaccepts by placing an object of a specific form into the output membrane. – If the output membrane of Πis different from its input membrane and the initial object placed into the output membrane does not satisfy the acceptance criterion, then Πrejects all inputs: Lacc(Π) = ∅. – If the output membrane of Πis the same as its input membrane, then Π will accept those inputs objects which satisfy the acceptance criterion for output objects. Therefore Πcan be made to accept any subset of Oby varying its acceptance criterion. These observations conclude the proof. To avoid trivial results, we assume in what follows that the procedure for extracting the result out of the output object is reasonably simple. As we have just seen, ΘU-mode-freeness is a very strong restriction. We will now consider an important subfamily of ΘU: non-denying modes. Given a P system Π, a mode ϑis non-denying if, for any configuration Cof Π,Appl(Π, C)6=∅implies that Appl(Π, C, ϑ)6=∅. The mode is called denying otherwise. We will use the notation Θ¬deny to refer to the subfamily of non-denying modes. 70 A. Alhazov et al. 7. Rudolf Freund. Asynchronous P systems and P systems working in the sequential mode. In Giancarlo Mauri, Gheorghe Paun, Mario J. P´erez-Jim´enez, Grzegorz Rozenberg, and Arto Salomaa, editors, Membrane Computing, 5th International Workshop, WMC 2004, Milan, Italy, June 14-16, 2004, Revised Selected and Invited Papers, volume 3365 of Lecture Notes in Computer Science, pages 36–62. Springer, 2004. 8. Rudolf Freund, Marian Kogler, and Marion Oswald. A general framework for regulated rewriting based on the applicability of rules. In Jozef Kelemen and Alica Kelemenov´a, editors, Computation, Cooperation, and Life - Essays Dedicated to Gheorghe Paun on the Occasion of His 60th Birthday, volume 6610 of Lecture Notes in Computer Science, pages 35–53. Springer, 2011. 9. Rudolf Freund and Sergey Verlan. A formal framework for static (tissue) P systems. In George Eleftherakis, Petros Kefalas, Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, editors, Membrane Computing, volume 4860 of Lecture Notes in Computer Science, pages 271–284. Springer Berlin Heidelberg, 2007. 10. Daniel T. Gillespie. Exact stochastic simulation of coupled chemical reactions. The Journal of Physical Chemistry, 81(25):2340–2361, 1977. 11. Sergiu Ivanov. A formal framework for clock-free networks of cells. International Journal of Computer Mathematics, 90(4):776–788, 2013. 12. Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA, 2010. 13. Grzegorz Rozenberg and Arto Salomaa, editors. Handbook of Formal Languages, 3 volumes. Springer, New York, NY, USA, 1997. 14. Drago¸s Sburlan. Clock-free P systems. In Pre-proceedings of the Fifth Workshop on Membrane Computing (WMC5), Milano, Italy, June 2004, pages 372–383, Milano, Italy, June 2004. 15. Bosheng Song, Mario J. P´erez-Jim´enez, and Linqiang Pan. An efficient time-free solution to SAT problem by P systems with proteins on membranes. J. Comput. Syst. Sci., 82(6):1090–1099, 2016. 16. Bosheng Song, Tao Song, and Linqiang Pan. Time-free solution to SAT problem by P systems with active membranes and standard cell division rules. Natural Computing, 14(4):673–681, 2015. 17. Bosheng Song, Tao Song, and Linqiang Pan. A time-free uniform solution to subset sum problem by tissue P systems with cell division. Mathematical Structures in Computer Science, 27(1):17–32, 2017. 18. Tao Song, Luis F. Mac´ıas-Ramos, Linqiang Pan, and Mario J. P´erez-Jim´enez. Timefree solution to SAT problem using P systems with active membranes. Theor. Comput. Sci., 529:61–68, 2014. 19. Bulletin of the International Membrane Computing Society (IMCS). http:// membranecomputing.net/IMCSBulletin/index.php. 20. The P Systems Website. http://ppage.psystems.eu/. Membrane Systems and Time Petri Nets Bogdan Aman1, P´eter Batty´anyi2, Gabriel Ciobanu1, Gy¨orgy Vaszil2 1Romanian Academy, Institute of Computer Science Blvd. Carol I no. 8, 700505 Ia¸si, Romania [email protected], [email protected] 2Department of Computer Science, Faculty of Informatics University of Debrecen Kassai ´ut 26, 4028 Debrecen, Hungary [email protected], [email protected] Summary. We investigate the relationship of time Petri nets and different variants of membrane systems. First we show that the added feature of “time” in time Petri nets makes it possible to simulate the maximal parallel rule application of membrane systems without introducing maximal parallelism to the Petri net semantics, then we define local time P systems and explore how time Petri nets and the computations of local time P systems can be related. 1 Introduction There has been several models applied for describing concurrency, communication and synchronization. Two of them are the graph-based model, known later as Petri nets, developed by C. A. Petri [11] and the tree-like model of embedded membranes called membrane or P systems invented by Gh. P˘aun [9]. Petri nets are state/transition systems: places are often used to contain information representing conditions in the system being modeled while transitions are used to represent events that can occur to modify the conditions. Some of the information, the input of the transition, is required for an event to happen, while some other information, the output of the transition, provides the result of the executed transition: they are the output of the transition. A Petri net is a bipartite graph: arcs point from input places to transitions and from transitions to places storing their outputs. There may be some situations where the modelling of a system by conditions and events is not completely satisfactory, for example, when the assumption that all the transitions can take place in an arbitrary order does not describe the system correctly. To model the situation when time delay must be taken into account time Petri nets (TPN) were developed. Concerning time Peri nets, several models were elaborated: time was associated with transitions, places or arcs, etc. We consider the approach adopted by Merlin [8] rendering time to transitions. By this 72 B. Aman et al. model, to every transition twe associate a closed interval [at, bt] such that at, bt∈Q≥0. The transition can fire, if it is enabled and its local time h(t) is such that at≤h(t)≤bt. We adopt the strong semantics, which means that a transition which is enabled either must be fired at some point of the associated interval or it becomes non enabled by firing of another transition. In general, time Petri nets are more powerful than ordinary Petri nets, since time Petri nets are able to simulate Turing machines while, for ordinary Petri nets, this is not possible. Membrane systems are parallel, distributed, synchronized models of computation where embedded membranes are organized in a tree like structure and computation takes place simultaneously in the different membranes in the forms of applications of rewriting rules. The rules evolve in a distributed manner: the application of a rule yields elements with labels, so called messages, which prescribe the exact place where the result of the rule application should move to. An element obtained by a rule application can either remain in the actual membrane, permeate to the parent membrane, or enter into one of its child membranes indicated by the rule. We consider here the basic model, that is, a membrane structure without dissolution rules. In addition we associate to each rule a time interval which gives a lower and an upper values for the time instance when the rule can be executed. We found technically simpler to consider every compartment as if a local stopwatch would operate in that compartment, though the same results could be obtained when we defined a global clock for synchronizing computational steps in the whole membrane system. We call our membrane systems local time membrane systems. In this paper we relate local time membrane systems to time Petri nets such that the image Petri net of a membrane system by this mapping is suitable for answering questions in connection with the membrane system. For example, we can heavily lean on results in the area of time Petri nets concerning questions of reachability, which asks whether a certain configuration of the membrane system can be achieved, or threshold problems, where the question is whether a state can be reached from another in a certain time, or simply finding the paths requiring minimum/ maximum time between any two reachable states (see Popova- Zeugmann [14]). There are several timed models for P systems in the literature (see [3], [4], [1]). The attempts for the simulation, up to the present, seem to take the approach similar to timed Petri nets ([6], [1], [2]), where certain values, the delay values, are assigned to rules. This means that the result of a rule application can appear only after that delay assuming a global clock synchronizes the computation of the system. Our model resembles much to that of time Petri nets: an interval is assigned to every rule and a clock local to each compartment synchronizes when the rule can be executed. A computational step is governed by a global clock: only when all membranes finish their action can a new step take place. Membrane Systems and Time Petri Nets 73 2 Membrane systems First of all, we discuss some terminology used in the sequel. A finite multiset over an alphabet Vis a mapping M:V→Nwhere Nis the set of non-negative integers, and M(a) for a∈Vis said to be the multiplicity of ain V. We say that M1⊆M2 if for all a∈V,M1(a)≤M2(a). The union or sum of two multisets over Vis defined as (M1+M2)(a) = M1(a) + M2(a), the difference is defined for M2⊆M1 as (M1−M2)(a) = M1(a)−M2(a) for all a∈V. The multiset Mcan also be represented by any permutation of a string w=aM(a1) 1aM(a2) 2. . . aM(an) n∈V∗, where if M(x)6= 0, then there exists j, 1 ≤j≤n, such that x=aj. The set of all finite multisets over an alphabet Vis denoted by M(V), the empty multiset is denoted by ∅as in the case of the empty set. A membrane system, or P system, is a tree-like structure of hierarchically arranged membranes embedded in the skin membrane as the outermost part of the system. Each region is delimited by a surrounding membrane, they can be arranged in a tree (cell-like [9]) structure or in a graph form (tissue-like [7] or neural-like [5]). In this paper we use the so-called symbol-object P systems [9] without dissolution, that is, each membrane has a label and enclosing a region containing a multiset of objects and rules and possibly some other membranes. The unique outer-most membrane is called the skin membrane. We assume the membranes are labelled by natural numbers {1, . . . , n}, and we use the notation mi for the membrane with label i. Each membrane mi, except for the skin membrane, has its parent membrane, which we denote by µ(mi). As an abuse of notation we use µboth for the parent function and both for denoting the structure of the membrane system itself. The contents of the regions of a P system evolve through rules associated with the regions. The computation of a P system is a locally asynchronous globally synchronous process: each multiset of objects in a region is formed locally by the rules attached to the regions, while a computational step of the whole system is a macro step: it finishes when all of the regions have finished their actions. In the variant we consider in this paper, the rules are multiset rewriting rules given in the form of u→vwhere u,vare multisets, and they are applied in a maximal parallel manner, that is, a region finishes its computation when no more rules can be applied in that computational step. In fact, the computational steps in the regions consist of two parts: first the rule application part and then comes a communication part where all the objects with labels find their correct places. The end of the computation of the system is defined by the following halting condition: a P system halts when no more rules can be applied in any of the regions; the result is a number, or a tuple of natural numbersthe number of certain objects in a membrane labelled as output. Definition 1. AP system of degree n≥1is Π= (O, µ, w1, . . . , wn, R1, . . . , Rn) where -Ois an alphabet of objects, 74 B. Aman et al. -µis a membrane structure of nmembranes, -wi∈ M(O),1≤i≤n, are the initial contents of the nregions, -Ri,1≤i≤n, are the sets of evolution rules associated with the regions; they are of the form u→vwhere u∈ M(O)and v∈ M(O×tar)where tar ={here, out}∪{inj|1≤j≤n}. Unless otherwise stated we consider the n-th membrane as the output membrane. A configuration is the sequence W= (w1, . . . , wn) where wkare the multiset contents of membrane mk( 1 ≤k≤n). Let R=R1∪R2∪ · · · ∪ Rn, where Ri={ri1, . . . , riki}is the set of rules corresponding to membrane mi. The application of u→v∈Riin the region imeans to remove the objects of ufrom wiand to add the new objects specified by vto the system. The rule application in each region takes place in a non-deterministic and maximally parallel manner. This means that the rule application phase finishes, if no rule can be applied anymore in any region. As a result, each region where rule applications took place, is possibly supplied with elements of the set O×tar. We call a configuration which is a multiset over O∪O×tar an intermediate configuration. If we want to emphasize that W= (w1, . . . , wn) consists of multisets over O, we say that Wis a proper configuration. Rule applications can be preceded by priority check, if priority relations are present. Let ρi⊆Ri×Ri1≤i≤nbe the (possibly empty) priority relations. Then r∈Riis applicable only if no r0∈Rican be applied with (r0, r)∈ρi. We may also denote the relation (r0, r)∈ρiby r0> r. Priority relations will be mentioned only in Remark 2. In the next phase the elements coming from the right hand sides of the rules of region ishould be added to the regions as specified by the target indicators associated with them. If rhs(r) contains a pair (a, here)∈V×tar, then aremains in region i, this is the region where the rule is applied. If rhs(r) contains (a, out)∈ V×tar, then ais added to the parent region of region i. In our membrane systems we assume that the results are formed in a designated membrane, the output membrane, of the system. Unless otherwise stated, we consider mnas the output membrane of the system. If rhs(r) contains (a, inj)∈V×tar for some region j, then ais added to the contents of region j. In the latter case µ(mj) = miholds. 3 The Petri net model By defining a time dependent Petri net model we followed the definition proposed by Popova-Zeugmann [12] and chose a model rendering time intervals to transitions along the original concept of Merlin [8]. First of all, we define the notion of untimed Petri net and then extend this concept to the timed version. Definition 2. A Petri net is a tuple U= (P, T, F, V, m0)such that 1. P,T,Fare finite, where P∩T=∅,P∪T6=∅and F⊆(P×T)∪(T×P), 2. V:F→N>0, 3. m0:P→N. Membrane Systems and Time Petri Nets 75 The elements of Pare called places and the elements of Tare called transitions. The elements of Fare the arcs and Fis the flow relation of U. The function Vis the multiplicity (weight) of the arcs and m0is the initial marking. We may occasionally omit the initial marking and simply refer to a Petri net as the tuple U= (P, T, F, V ). We stipulate that, for every transition t, there is a place psuch that V(p, t)6= 0. In general, a marking is a function m:P→N. Let x∈Por x∈T. The pre- and postsets of x, denoted by •xand x•, respectively, are defined as •x= {y|(y, x)∈F}and x•={y|(x, y)∈F}. Each arc has an incoming and outcoming multiplicity denoted as follows: Definition 3. Let tbe a transition. We define below two markings, t−and t+, as multisets of places, which govern when a transition can be fired and how many tokens are added to the place pupon firing the transition, respectively. t−(p) = V(p, t),if (p, t)∈F, 0 otherwise ,t+(p) = V(t, p),if (t, p)∈F, 0 otherwise . A transition is said to be enabled, if t−(p)≤m(p) for all p∈P. Applying the notation Mt=t+−t−, we are able to define a firing of the Petri net U= (P, T, F, V ). Definition 4. Let U= (P, T, F, V, m0)be a Petri net and let mbe a marking in U. A transition t∈Tcan fire in m(notation: m−→t), if tis enabled in m. After the firing of t, the Petri net will obtain the new marking m0, where m0=m+Mt. Notation: m−→tm0. We obtain time Petri nets, if we add to the Petri net model information about time attached to transitions. Intuitively, the time associated to a transition will denote the last time when the transition or a transition with common preplace was fired. Though the definitions could be extended to unbounded time intervals also, we are concerned with bounded time intervals this time. Definition 5. A time Petri net (TPN) is a 6-tuple N= (P, T, F, V, m0, I)such that 1. the 5-tuple S(N)=(P, T, F, V, m0)is a Petri net, 2. I:T→Q≥0×Q≥0and, for each t∈T,I(t)1≤I(t)2holds, where I(t) = [I(t)1, I(t)2]. We call I(t)1and I(t)2earliest and latest firing times belonging to t, respectively. Notation: eft(t),lft(t). A function m:P→Nis called a p-marking of N. Observe that talking about ap-marking of Nis the same as talking about a marking of S(N), where S(N) is called the skeleton of Nand, roughly speaking, it is the untimed Petri net obtained from Nby omitting every reference to time. 76 B. Aman et al. Definition 6. 1. A transition marking (or t-marking) is a function h:T→ R≥0∪ {#}. 2. Let N= (P, T, F, V, mo, I)be a time Petri net, map-marking and hatmarking in N. A state in Nis a pair u:= (m, h)such that a) (∀t∈T)(t−m→h(t) = #), b) (∀t∈T)(t−≤m→h(t)∈R≥0∧h(t)≤lft(t)). The initial state is the pair u0= (m0, h0), where m0is the initial marking and h0(t) = 0,if t−≤m0, # otherwise . Definition 7. A transition tis ready to fire in state u= (m, h)(in notation: u−→t), if tis enabled and eft(t)≤h(t). We define the result of the firing of a transition that is ready to fire. Definition 8. Let tbe a transition and u= (m, h)be a state such that u−→t. Then the result of the firing of tis a new state u0= (m0, h0), such that m0=m+4t and h0(ˆ t) =    h(ˆ t),if (ˆ t−≤m, ˆ t−≤m0and •ˆ t∩•t=∅)or t=ˆ t, # if ˆ t−m0, 0 otherwise . In words, the firing of a transition has multiple effects. First of all, it changes the t-marking of the system as it is customary by simple Petri nets. Moreover, the time values attached to the transitions may also change. If ˆ twas enabled before the firing of transition tand ˆ tremains enabled after the firing, moreover ˆ thas no common preplace with the transition which has just been fired, then the value h(ˆ t) for ˆ tremains unchanged. The value h(ˆ t) remains the same even if ˆ t=t. If ˆ tis newly enabled with the firing of transition tor ˆ thas common preplace with tand ˆ tdiffers from t, then we have h(ˆ t) = 0. If ˆ tis not enabled after firing of transition t, then h(ˆ t) = #. Observe that we adopt a stronger condition for hto preserve the value for a transition ˆ tupon firing with transition t. We are not content with the fact that ˆ t should be newly enabled in order to have h(ˆ t) = 0 in the subsequent computational step, but we also demand that tand ˆ tshould not have common preplaces. To ensure multiple executions of the same transition, if ˆ t=t, then h(ˆ t) retains its value after the firing step. Besides the firing of a transition there is another possibility for a state to alter, and this is the time delay step. Definition 9. Let tbe a transition and u= (m, h)be a state and τ∈R+. Then elapsing of time with τis possible for the state u(in notation: u−→τ), if for all t∈T,h(t)6= # implies h(t) + τ≤lft(t). Then the result of the elapsing of time by τis defined as follows: u−→τu0= (m0, h0), where m=m0and h0(ˆ t) = h(ˆ t) + τ, if ˆ t−≤m0for an arbitrary ˆ t∈T, # otherwise. Membrane Systems and Time Petri Nets 77 Observe that the definition of the result of a time elapse ensures that we are not able to skip a transition when it is enabled: a transition cannot be made not enabled by a time jump. Finally, we define the notion of a feasible run in a time Petri net. Definition 10. Let N= (P, T, F, V, mo, I)be a time Petri net, assume σ= t1. . . tnis a sequence of transitions and τ=τ0τ1. . . τn(τi∈R≥0)be a sequence of times. Then σ(τ)τ0t1τ1. . . tnτnis called a run. σ(τ)is a feasible run, if there are states s= (m, h)and s0= (m0, h0)such that s−→∗ σ(τ)s0. We may omit the argument τfrom σ(τ)if it is clear from the context. Obviously, classic Petri nets can be obtained when h(t) = [0,0] for every transition and no time delay step is ever made. 4 Relating the Petri net model to the membrane system First, we show how to establish a correspondence between the P system model without time and the model of time Petri nets. As the first step we give the underlying structure of the Petri net associated to a membrane system. The correspondence described below seems to have appeared first by Kleijn, Koutny and Rozenberg [6]. They define the correspondence by limiting the results of the Petri net computations only to those which can be obtained by a sequence of maximal parallel or maximally enabled transition steps. A step is a multiset of transitions and a transition is maximally enabled, if it is enabled and is not a proper subset of an enabled step. They establish a close correspondence between Petri nets with maximally enabled (max enabled) steps and membrane systems. Moreover, other semantics like locally enabled steps or minimal enabled steps could be considered. In this case we preserve the original semantics for Petri nets: the fireable transitions can be executed in any order. This involves that we have to make essential use of the timed model, since ordinary Petri net model is not Turing complete in contrast to the general membrane system. Definition 11. Let Π= (O, µ, w1, . . . , wn, R1, . . . , Rn)be a membrane system. Then we define the following places and transitions for the Petri net. 1. P=P0∪P∗ 0∪ {sto, ste, sem}, where P0=V× {1, . . . , k}and P∗ 0=V∗× {1, . . . , k}. We set m0(p) = wj(a)for every place p= (a, j). Intuitively, the places V× {1, . . . , k}correspond to the objects of Vlabelled by the indexes of the membranes and the places in V∗× {1, . . . , k}correspond to the objects on the right hand sides of Ri(1 ≤i≤n)labelled by messages. The places ste, sto, sem are additional places which serve for the synchronization of the Petri net model. 2. T=T0∪T∗ 0∪ {to, te, t1 sem, t2 sem}, where the sets of transitions T0and T∗ 0are detailed in the subsequent parts of the definition and {to, te, t1 sem, t2 sem}are auxiliary transitions to be specified later. Let rl∈Ri, where l∈ {1, . . . , nki}. 78 B. Aman et al. Then let ti ldenote the transition corresponding to rland T0={ti l|1≤i≤ n, 1≤l≤ki}. A transition ti lconnects elements of P0to P∗ 0: if p= (a, j), then V(p, ti l) = lhs(rl)(a), if i=j, and V(p, ti l) = 0 otherwise. Furthermore, if p∗= (a∗, j),V(ti l, p∗) = rhs(rl)(a), if i=j,V(ti l, p∗) = rhs(rl)(a, out), if j=parent(i)and V(ti l, p∗) = rhs(rl)(a, inj), if i=parent(j)and V(ti l, p∗) = 0otherwise. Likewise, T∗ 0={si j|1≤i≤k, 1≤j≤n}are such that {•(si j)|1≤i≤k, 1≤j≤n}=P∗ 0,{(si j)•|1≤i≤k, 1≤j≤n}=P0and, if ai∈Oand 1≤j≤n, then p∗= (ai, j)∗and V(p∗, si j) = V(si j,(ai, j)) = 1 and all the other values are 0. The transitions t1 sem and t2 sem, belonging to the semaphore, will be treated in the section. 3. The intervals belonging to the elements of T=T0∪T∗ 0are [0,0], the transitions aiming for the synchronization have various time intervals to be specified later. In words, we simulate the rule rl∈Riwith transition ti lsuch that the weights of the arcs reflect the multiplicities of the elements in compartment i, and the transitions sk jensure the correct reordering of the elements with messages when the rewriting phase is finished. If we term the rule application phase as the odd and the communication phase as the even part of the operation, we obtain two Petri nets for the subsequent phases of the simulation, which are illustrated in Figures 1 and 2. A little more detailed, the complete Petri net acts as follows. The two main sets for the places correspond to the objects of the membrane system. If ai∈V has kioccurrences in mj, then, for p= (ai, j), m(p) = ki. Likewise, assume at the end of a rule application phase we have k0 ioccurrences of (ai, here) in mj, and k00 ioccurrences of (ai, out) in ml, where j=parent(l) and k000 icopies of (ai, inj) for l=parent(j), then m(p∗) = k0 i+k00 i+k000 i, where p∗= (ai, j)∗. At the rule application phase the element stocontrols the process: if there are any transitions that are enabled, then they are executed. Otherwise a time elapse is applied and a token from stois passed over to sem at time 1. The situation is similar with the communication phase: if every element has found its correct place, then no more transition sj iis possible and stegives control to sem by passing a token to sem at time instance 1. We ensure the globally asynchronous locally synchronous character of the membrane system for the Petri net by defining a semaphore which governs the distinct groups of membrane transitions, like rewriting phase, where objects are replaced in accordance with rewriting rules, or communication phase, where objects labelled with tags inj, here, out find their correct places. In what follows we define the timed part of the Petri net that provides the synchronization. Assume the semaphore is denoted by the tuple Sem = ({sem}, R, Fsem, Vsem, I). In some sense the semaphore divides the rule application and communication parts of the operation of the P system. The place sem of the semaphore is the place where this choice takes place. The place sem obtains either one or two tokens. Membrane Systems and Time Petri Nets 79 stop1p2 to [1,1] t1 [0,0] sem p∗ 1p∗ 2 2 Fig. 1. The Petri net simulating the rule application part of a membrane computational step. sem p1p2 te [1,1] 1 t∗ 1 [0,0] t∗ 2 [0,0] step∗ 1p∗ 2 Fig. 2. The Petri net simulating the communication part of a membrane computational step. 86 B. Aman et al. rules corresponding to the chosen transitions form a maximal parallel set of rules. If at the end of the rule application phase at least one rule remains that could be applied, then our choice is obviously not a maximal parallel set of rules. In order to ensure the correct simulation, in this case the Petri net enters into an infinite loop of transitions when reaching state perp˜ tprovided ˜ tcould be applied. Otherwise, control is given back to the semaphore. Figure 5 details the Petri net which is in fact a sub net of the one in Figure 4. qi Bp1p2 tfini [1,1] ¯ t [0,0] finiperp¯ t 2 [0,0] Fig. 5. The Petri net deciding whether a maximal parallel set of rules is reached. Finally, Figure 6 gives an overall picture of the odd part of the simulating Petri net. The place stostimulates the odd phase and tokens are immediately distributed among the places qi 0, which initiate the simulations of the computations in membranes mi(1 ≤i≤n). When the computation in miis over, in the simulating Petri net the place finiobtains a token. If all the places fini(1 ≤ i≤n) have collected their tokens, then a token is passed over to sem and a new computational phase begins. We remark that the construction above gives a general method for simulating any time Petri net defined with the weak semantics by a time Petri net understood with the strong semantics. The case for the membrane system with the strong semantics is possibly a bit simpler, since it is closer to the original semantics of the Petri net model. We define in the next definition the simulating Petri net for a local time membrane system with the strong semantics. The construction is very similar to the ones of the previous subsection, probably it is a little bit easier this time. The only difficulty is to tell when a maximal parallel step is finished. For this purpose, before choosing Membrane Systems and Time Petri Nets 87 st0 [0,0] [0,0] . . . [0,0] q1 0q2 0 . . . qn 0 . . . fin1fin2 . . . finn [0,0] sem Fig. 6. The overall structure of the Petri net for the weak semantics the next transition, we implement a test whether there are transitions that could be executed. This involves creating a new copy of the Petri net simulating the left hand sides of the membrane system rules. Moreover, to keep ourselves to the interpretation of the membrane computational step by distinguishing the computational sequences in the different compartments, we assume that there are nsub Petri nets modelling the computations in the different membranes. We detach, as usual, the odd and even phases of the computation. In the odd phase, the token in stois immediately distributed to the places sti ohence initializing the computation in the sub Petri nets corresponding to membranes mi. Definition 18. Let Π= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system with the strong semantics. 88 B. Aman et al. 1. Pcontains P0and P∗ 0, where P0=V× {1, . . . , n},P∗ 0=V∗× {1, . . . , n}, where a∈Vand (1 ≤j≤n)are in Definition 11. As usual, P0represents the actual configuration of the membrane system. We set m0(p) = wj(a)for every place p= (a, j). As before, the places in V×{1, . . . , n}correspond to the objects on the left hand sides of Ri(1 ≤i≤n)of the membrane rules, while the elements of V∗× {1, . . . , n}correspond to the objects on the right hand sides of the membrane rules labelled by messages. There are auxiliary places, namely those of the semaphore and ste,sti o,cati: they govern the simulation of the rule application and communication phases. 2. Tconsists of T0,T∗ 0,e T0and some auxiliary transitions. As before, let rl∈Ri, where l∈ {1, . . . , nki}. Then let ti ldenote the transition corresponding to rl and T0={ti l|1≤i≤n, 1≤l≤ki}. A transition ti lconnects elements of P0to P∗ 0: if p= (a, j), then V(p, ti l) = lhs(rl)(a), if i=j, and V(p, ti l) = 0 otherwise. Furthermore, if p∗= (ai, j)∗, then V(ti l, p∗) = rhs(rl)(a), if i=j, V(ti l, p∗) = rhs(rl)(a, out), if i=parent(j)and V(ti l, p∗) = rhs(rl)(a, inj), if j=parent(i)and V(ti l, p∗)=0otherwise. Moreover, (cati, ti l),(ti l, sti o), (sti o, tcati),(tcati, cati)∈F. T∗ 0={si j|1≤i≤k, 1≤j≤n}is defined as before: we let {•(si j)1 ≤ i≤k, 1≤j≤n} | =P∗ 0,{(si j)•|1≤i≤k, 1≤j≤n}=P0and V((p∗ i, j), si j) = V(si j,(ai, j)) = 1, where p∗ i= (ai, j)∗, and all the other values be 0. As to the auxiliary places and transitions, sti oand stehave to check whether there are transitions left to fire. For stethis is easy: steconnects to each transition in T∗ 0, that is, (ste, si l),(si l, ste)∈Fand steconnects to sem by (ste, tre), (tre, sem)∈F. The places sti oneed to make a similar check concerning maximal parallel execution: (sti o,˜ ti l)∈F,(˜ ti l, cati)∈Fand ˜ ti lare such that the connections with the elements of P0are the same as in the case of P0and T0 with the same multiplicities, as well. However, ˜ ti ldo not point to P∗ 0, they give back all the tokens to P0after any of the transitions ˜ ti lhas been fired. When no transition ˜ ti lis able to fire, sti oforwards a token to finiand, when each fini (1 ≤i≤n)possesses a token, they give control back to sem by (fini, mono), (mono, sem)∈F. That is, monofires only if every sub Petri net assigned to membrane mifinishes its computation. 3. Concerning the intervals: the intervals belonging to the elements of T∗ 0are [0,0]. If ti l∈T0, then I(ti l) = I(ri l). Furthermore, I(fini) = I(fine) = [1,1]. All the remaining intervals are [0,0]. The semaphore is the same as by the case of the core model. We illustrate the sub Petri net corresponding to miin Figure 7. Let Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I) be a local time membrane system. If Πis considered with the weak semantics, then let Nw(Π) denote the time Petri net associated to Πaccording to Definition 17. If Πis understood with the strong semantics, then let Ns(Π) denote the Petri net assigned to Πin accordance with Definition 18. Furthermore, if (w, T) is a proper configuration of Π, let (ν(w), ν(T)) be the configuration of Nw(Π) or of Ns(Π), where Membrane Systems and Time Petri Nets 89 sti ocatip1p2 fini [1,1] t] 1 [0,0] t1[I(t1)−,I(t1)+] sem p∗ 1p∗ 2 2 Fig. 7. The Petri net for a local time membrane system with the strong semantics ν(w)(ai, j) = w(j)(i) and ν(T)(ti l) = T(rl), where rl∈Ri. In addition, if p∗= (a∗ i, j), let ν(w)(p∗) = 0, as (w, T) is a proper configuration. Moreover, if W= (w0,T0)⇒(w1,T1)⇒. . . ⇒(wk,Tk) is a configuration sequence of Π, then ν(W)=(ν(w0), ν(T0)) −→ (ν(w1), ν(T1)) −→ . . . −→ (ν(wk), ν(Tk)) is the corresponding sequence of configurations of Nw(Π) or Ns(Π). If Wis a sequence of proper configurations, then we omit the values Tiand ν(Ti) from the configurations (w, T) and (ν(w), ν(T)i), respectively, since, in this case Tj=T0, where T0(r) = 0 for every r∈R. Theorem 3. Let Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I)be a local time membrane system. 1. Let W=w0⇒w1⇒. . . ⇒wkbe a computational sequence with the weak semantics. Then w0⇒∗ Wwk⇔Nw(w0)−→∗ ν(W)Nw(wk). Moreover, τ(ν(W)) = τ(W)+3k, where τ(W)and τ(ν(W)) are the total time for Wand ν(W), respectively. 2. Let W=w0⇒w1⇒. . . ⇒wkbe a computational sequence with the strong semantics. Then w0⇒∗ Wwk⇔Ns(w0)−→∗ ν(W)Ns(wk). Moreover, τ(ν(W)) = τ(W)+3k, where τ(W)and τ(ν(W)) are the total time for Wand ν(W), respectively. 90 B. Aman et al. Proof. We treat the case of the weak semantics: we give a sketch for the proof of the correctness of our simulation. Assume Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I) is a local time membrane system, let W=w0⇒w1⇒. . . ⇒wkbe a computational sequence with the weak semantics. We prove the theorem by induction on k. -k= 0: there is nothing to prove. -k=l+ 1: Assume we have the statement for l, that is, for the computational sequence Wl=w0⇒σ1w1⇒σ2. . . ⇒σlwlthere exists ξl=m0⇒ m1⇒. . . ⇒mlsuch that µl=ν(wl) and τ(ν(ξl)) = τ(Wl) + 3 ·l, where, for any proper configuration wof Π,ν(w) is defined as above. If qis any place not in P0, then ν(q) = 0, except for sem, where ν(w)(sem) = 1. By the construction of the Petri net h(ti l) = I(ri l) also holds. We extend the correspondence νto the intermediate configurations, as well. The values for the elements of P0are defined as before. As to the values of P∗ 0: ν(w)(a∗ i, j) = w(j)(ai, here) + w(µ(j))(ai, inj) + Pj=µ(l)(ai, out). Let σ(i,s)= τ0r1τ1r2. . . rsτs+1, where r1, . . .,rs∈Ri, be a segment of the selection of mi of length swith the corresponding configurations ((w1,T1),...,(ws,Ts)). Then ξ(i,s)=ν(σ(i,s)) = τ01 . . . τ0k0t1τ11 . . . τ1k1t2. . . tsτ(s+1)1 . . . τ(s+1)ks+1 , where tj correspond to rjin Nw(Π) and τj=τj1+. . .+τjkj, is a computation in Nw(Π). Assume ((m1, h1),...,(ms, hs)) is the sequence of states corresponding to ξi,s, then we claim that ν(w1), . . . , ν(ws) define exactly the same t-markings. For the correspondence of the configurations and t-markings it is enough to prove that, if rcan be executed, then tis ready to fire provided tis assigned to r. By Fact 2, it is enough to observe that Ti(r) = j+afor some j∈Nsuch that r∈Ri jand 0 ≤a≤1, and i− t≤a≤i+ t, where [i− t, i+ t] is the interval corresponding to tas the image of r∈Ri jin accordance with Definition 17. The statement can be proved by examining the various cases for the next step in σi,s.  The converse of the theorem holds, too. We state it in a proposition. Proposition 1. Let N= (P, T, F, V, m0, I)be a time Petri net. Then the following statements are valid. 1. Let Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I)be be a local time membrane system, assume N=Nw(Π). Then, for any proper computational sequence ξof N, there exists computational sequence Wof Πwith respect to the weak semantics such that ξprovides exactly the same output as W. Moreover, τ(ξ) = τ(W) + 3k, where τ(W)and τ(ξ)are the total time for Wand ξ, respectively. 2. Let Π= (V, µ, u1, . . . , un, R1, . . . , Rn,I)be be a local time membrane system, assume N=Nw(Π). Then, for any proper computational sequence ξof N, there exists computational sequence Wof Πwith respect to the strong semantics such that ξprovides exactly the same output as W. Moreover, τ(ξ) = τ(W) + 3k, where τ(W)and τ(ξ)are the total time for Wand ξ, respectively. Membrane Systems and Time Petri Nets 91 Remark 2. We remark that local time weak semantics does not appear to add anything to the computational power of the membrane system, however local time with the strong semantics seems to increase the computational strength of the P system. We conjecture that, by a modification of a proof of P˘aun [10] showing that membrane systems with catalytic rules together with priority define recursively enumerable sets of numbers even with two membranes, it might not be difficult to prove that local time membrane systems with catalytic rules and with the strong semantics define recursively enumerable sets of numbers with two membranes. It is not clear to us, however, how the exact strength of a local time membrane system with the strong semantics could be depicted. 7 Applications The constructions of the previous section makes us possible to apply the results elaborated for time Petri nets for the case of local time membrane systems. Notation 4 Let Π= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system. We apply the notation Π=Π?, where ?∈ {w, s}stands for either the weak semantics or the strong semantics, respectively. Definition 19. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system. 1. A (possibly intermediate) configuration (w, T)is integer valued, if T(r)∈N for every r∈R. 2. Let mibe a membrane of Π?for some 1≤i≤n. Let σibe a run for mi. Then σiis integer valued if all of its intermediate configurations are integer valued. 3. Let W=w0⇒. . . ⇒wkbe a computational sequence for Π?. Then Wis integer valued, if, for every wi, every run of wiis integer valued. Observe that, given a membrane system Π?and a computational sequence W, the condition that Wis integer valued is equivalent to the requirement that all the time elapses in every run of Ware integers. Proposition 2. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system and let w0be a configuration reachable from w. Then w0is integer reachable from w. Proof. Follows from the main theorem together with the corresponding theorem for time Petri nets presented by Popova-Zeugmann ([13], [14]).  Definition 20. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system. Then Π?is bounded, if there exists K > 0such that, for every configuration wof Π?,|w(j)|< K (1 ≤j≤n). In other words, Kis an upper bound for the number of elements in every compartment with regard to any configuration w. 92 B. Aman et al. Proposition 3. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system, assume Π?is bounded. Then the reachability problem for Π?is decidable. Proof. Follows from Proposition 2.  Proposition 4. Let Π?= (V, µ, w1, . . . , wn, R1, . . . , Rn,I)be a local time membrane system, assume w0is reachable from w. Then the minimum and maximum distances between wand w0are integers. 8 Conclusions In this paper we examined the connections between two models of computations, namely, the membrane systems introduced by P˘aun [9] and time Petri nets defined along the lines of the papers of Popova-Zeugmann ([12],[13]). First of all, we presented a simulation of membrane systems without dissolution by time Petri nets. The novelty in our result is the fact that the simulating Petri nets manage to retain the locality of firing: transitions can be fired one after the other without structural control, like maximal parallelism, imposed on the order of their execution. Next, we defined local time membrane systems on the analogy of time Petri nets, equipping the computational model with two types of semantics. We showed that both kinds of local time membrane systems can be simulated by time Petri nets with the strong semantics. Finally, we mentioned some statements concerning local time membrane systems that are straightforward consequences of the similar results for time Petri nets by reason of the simulations. References 1. B. Aman, G. Ciobanu, Adding Lifetime to Objects and Membranes in P Systems. International Journal of Computers, Communications and Control, 5(3) (2010) 268– 279. 2. B. Aman, G. Ciobanu, Verification of membrane systems with delays via Petri nets with delays. Theoretical Computer Science, 598(C) (2015) 87–101. 3. M. Cavaliere, D. Sburlan, Time and Synchronization in Membrane Systems. Fundamenta Informaticae, 64(1) (2005) 65–77. 4. M. Cavaliere, D. Sburlan, Timeindependent P Systems Towards a Petri Net Semantics for Membrane Systems. Lecture Notes in Computer Science, volume 3365, International Workshop on Membrane Computing, WMC 2004, 239–258, Springer Verlag, Berlin, 2005. 5. M. Ionescu, Gh. P˘aun, T. Yokomori. Spiking Neural P Systems. Fundamenta Informaticae, 71 (2006) 279–308. 6. J. H. C. M. Kleijn and M. Koutny and G. Rozenberg, Towards a Petri Net Semantics for Membrane Systems. Lecture Notes in Computer Science, volume 3850, International Workshop on Membrane Computing, WMC 2005, 292–309, Springer Verlag, Berlin, 2005. Membrane Systems and Time Petri Nets 93 7. C. Mart´ın-Vide, Gh. P˘aun, J. Pazos, A. Rodr´ıguez-Pat´on. Tissue P Systems. Theoretical Computer Science, 296 (2003) 295–326. 8. P. M. Merlin, A Study of the Recoverability of Computing Systems. PhD thesis, University of California, Irvine, CA, 1974 9. G. P˘aun, Computing with Membranes. Journal of Computer and System Sciences, 61(1) (2000) 108–143. 10. G. P˘aun, Membrane Computing - An Introduction, Springer Verlag, Berlin, 2002. 11. C. A. Petri, Kommunikation mit Automaten. Dissertation, Universit¨at Hamburg, Hamburg, 1962. 12. L. Popova, On time Petri nets. Journal of Information Processing and Cybernetics, EIK, 27(4) (1991) 227–244. 13. L. Popova-Zeugmann, Essential States in time Petri nets, Informatik- Berichte der HUB, Nr. 96, 1998. 14. L. Popova-Zeugmann, Time and Petri Nets, Springer Verlag, Berlin, 2013. Two Notes on APCol Systems Lucie Ciencialov´a1,2and Ludˇek Cienciala1,2 1Research Institute of the IT4Innovations Centre of Excellence, Faculty of Philosophy and Science, Silesian University in Opava, Czech Republic 2Institute of Computer Science Faculty of Philosophy and Science, Silesian University in Opava, Czech Republic [email protected] [email protected] Summary. In this work, we continue our research in the field of string processing membrane systems - APCol systems. We focus on a relation of APCol systems with PM colonies - colonies whose agents can only perform point mutation transformations of the common string, in a vicinity of the agent. The second part is devoted to a connection of APCol systems and logic circuits using AND, OR and NOT gates. 1 Introduction There are many different theoretical computational models, where are independent agents engage in a shared environment or interact with it directly. In this paper, we continue our research in the examination of connections between such models. In [26] our research started with the comparison of eco-colonies – composed from components (grammars) acting in a string, the string is also evolved by environmental rules (0L scheme), P colonies and eco-P colonies – membrane systems with one-membrane agents and a unordered environment. In this paper, we continue our study with APCol systems – the model related closely to P colonies – PM colonies and logic circuits. APCol systems are formal models of a computing device combining properties of membrane systems and colonies - parallel distributed systems of formal grammars. Membrane systems (called P systems, [24]) are biologically inspired distributed multiset rewriting systems that are characterised by massive parallelism and simple rules. APCol systems were introduced in [4] The reader can find more information about membrane systems in [23] and in [17] can a reader find details on grammar systems theory. An APCol system is formed from agents - collections of objects embedded in a membrane - and shared environment - string. Agents are equipped with programs composed of rules that allow agents to interact with objects that are placed inside them and they form a string. The number of objects inside each agent is set by definition and it is usually very low up to 3. The string is processed by agents 102 Two Notes on APCol Systems If the answer is positive, it tries to solve collision. The third phase is performing phase, when APCol system agent rewrite active and inactive agents into objects in the way corresponding to executed rules. If there is more than one applicable rule ( PM-colony is non-deterministic) executed rule is chosen non-deterministically. In the last phase the APCol system agent non-deterministically chooses whether computation will end and erase all occurrences of PM-colony agents or the system will continue with the next derivation step - to ensure that APCol system can halt after every simulated derivation step of PM-colony. Theorem 1. To every PM-colony πthere exist APCol system that can generate all states of PM-colony. Proof. Let π= (E; #; N;>;R1;. . . ;Rn) be a PM-colony operating on a string w0∈(E∪N)∗. We construct APCol system Π= (O, e, A1, . . . , Am),where m equals to number of rules in πplus 6, as follows: The agent A1has initial configuration ee and the subset of programs to initialize simulation. A1 1.he→#0;e→Ti 2.h#0↔#; T↔aifor all a∈E∪N∪ {#} 3.h#→P;a→ai 4.hP↔e;a↔Tifor all a∈E∪N∪ {#} 5.hT→↑;e→ei APCol system starts computation on the string #w0#=#aw1#. Agent A1 is in the initial configuration ee. In the first step it rewrites its contents to #0T using the program 1. At the second step The agent replace the first two symbols from the string by its contents. After second step the contents of the agent A1#a and the string in the environment is #0T w1#. In the next step agent rewrites # to Pand exchange its contents by Tfrom a string. The configuration of the agent is eT and the string has a form #0P aw1#. The agent A2is supporting agent; It generates the auxiliary objects consumed by agent A1. Set P2contains following programs: A2 A. he→↓;e→ei B. h↓↔ P;e→ei step string agent A1agent A2 applicable programs of A1 applicable programs of A2 0.#aw1#ee ee 1. A. 1.#aw1# #0T↓e2.− 2.#0T w1# #a↓e3.− 3.#0T w1#P a ↓e4.− 4.#0P aw1#eT ↓e5. B 5.#0↓aw1#↑e P e 6. C L. Ciencialov´a, L. Cienciala 103 Phase 1. - Context detection After symbol ↓appears in the string #0↓aw1#, agent A1goes through the string from the left to the right end and rewrites occurrences of PM-colony agents Aby symbols aAbwhere a, b are neighbouring symbols (aAB is substring of the input string). A1 6.h↑↔↓;e↔ai for all a∈E∪N 7.ha↔↑;↓↔ ei for all a∈E 8.a→A;↓→ L for all a∈N 9.A→A;L↔↑ A2 C. hP→L0;e→ei D. hL0↔b;e↔Li for all b∈E∪iNj i, j ∈E∪N∪ {#} E. hb→b;L→Lbi F. hb↔L0;Lb↔ei G. hL00 →R0;e→ei A1 10.A→A;↑↔ L0 11.A→A;L0→L00 12.A→A;L00 ↔↑ 13.A→A;↑↔ Lb0 14.A→b0A;Lb0→R 15.hb0A→b0A;R↔↑i 16.hb0A→b0A;↑↔ R0i 17.hb0A→b0A;R0→R00i 18.hb0A→b0A;R00 ↔↑i 19.hb0A→b0A;↑↔ Rc0i where b, c ∈E∪N 20.hb0A→b0Ac0;Rc0→↓i where b, c ∈E∪N 21.hb0Ac0↔e;↓↔↑i where b, c ∈E∪N 22.h↓→ Ex; # →#i 23.hEx↔↑; # ↔ei A2 H. hR0↔R;e↔ci c∈E∪N I. hR→Rc;c→ci J. hRc↔R00;c↔ei K. hR00 →L0;e→ei Agents A1and A2helps each other to change all occurrences of PM-colony agents to more complex symbols capturing agent neighbouring symbols. In following table, a, b ∈Eand A∈N. 104 Two Notes on APCol Systems step string agent A1agent A2 applicable programs of A1 applicable programs of A2 5.#0↓aAbw1#↑e P e 6. C. 6.#0↑Abw1#↓a L0e7.− 7.#0a↓Abw1#↑e L0e6.− 8.#0a↑bw1#↓A L0e8.− 9.#0a↑bw1#AL L0e9.− 10.#0aLbw1#A↑L0e−D. 11.#0L0bw1#A↑aL 10. E. 12.#0↑bw1#AL0aLa11.− 13.#0↑bw1#AL00 aLa12.− 14.#0L00bw1#A↑aLa−F. 15.#0aLabw1#A↑L00e13. G. 16.#0a↑bw1#ALaR0e14.− 17.#0a↑bw1#aAR R0e15.− 18.#0aRbw1#aA↑R0e−H. 19.#0aR0w1#aA↑Rb 16. I. 20.#0a↑w1#aAR0Rbb17.− 21.#0a↑w1#aAR00 Rbb18.− step string agent A1agent A2 applicable programs of A1 applicable programs of A2 22.#0aR00w1#aA↑Rbb−J. 23.#0aRbbw1#aA↑R00e19. K. 24.#0a↑bw1#aARbL0e20.− 25.#0a↑bw1#aAb↓L0e21.− 26.#0aaAb↓bw1#↑L0e6.− Phase 2. - Determining agents as active or inactive In the second phase agents A1and A3read the string from right to the left and they search for conflicts. Inactive agents are marked by yXz, active agents has the label in a form yXz. A1 24.h↑→⇑;e→li 25.hl→⇓;⇑↔ #i 26.h⇓↔ e; # ↔⇑i A3 i. he→l;e→ei ii. hl↔ Ex;e→ei iii. hEx→m;e→ei iv. hm↔⇓;e→ei v. h⇓→ e;e→ei A1 To skip a∈E 27.h⇑↔ a;e↔mi 28.hm↔ e;a↔⇑i L. Ciencialov´a, L. Cienciala 105 A1 If A1consumes bAc, A ∈N;b, c ∈E∪N∪ {#} 29.h⇑↔ bAc;e→mi 30.hbAc→bA0 c;m→mAi bA0 c=bAcfor b, c ∈Eor b, c ∪Nand b<A,c<A bAcotherwise 31.hmA↔⇑;bA0 c↔ei A1 If mAis sent to the string and next symbol is a∈E 32.h⇑↔ a;e↔mAi 33.hmA→⇓A;a→ai 34.h⇓A↔e;a↔⇑i A1 If mAis sent to the string and next symbol is bBc 35.h⇑↔ bBc;e↔mAi 36.hbBc→bB0 c;mA→Yi; bB0 c=bBcfor B > A and {b, c ∈Eor b, c ∈Nand b < A, c < A} bBcotherwise Y=*mBfor B > A mAfor A>B m{A,B}otherwise 37.hX↔⇑;bB0 c↔ei A1 If mM(Mis a subset of N) is sent to the string and next symbol is bBc 350.h⇑↔ bBc;e↔mMi 360.hbBc→bB0 c;mM→Yi; bB0 c=*bBcif Bis greatest element of M∪ {B}and b, c ∈Eor b, c ∪Nand b, c is not greatest element of M∪ {b, c} bBcotherwise Y=*mBfor B > A mAfor A>B m{A,B}otherwise 370.hX↔⇑;bB0 c↔ei A1 If ⇓Ais sent to the string and next symbol is a∈E 38.h⇑↔ a;e↔⇓Ai 39.ha→a;⇓A→mi ; 40.hm↔⇑;a↔ei 106 Two Notes on APCol Systems A1 If ⇓Ais sent to the string and next symbol is bBc 41.h⇑↔ bBc;e↔⇓Ai 42.hbBc→bB0 c;⇓A→Xi; bB0 c=bBcfor B > A and {b, c ∈Eor b, c ∪Nand b < A, c < A} bBcotherwise X=*mAfor A>B BAfor B > A eAotherwise 43.hX↔⇑;bB0 c↔ei If the next symbol to be checked is boundary object #0the agent A4finishes the second phase. A5 AA. he→D;e→ei AB. hD↔#0;e↔Xi;X∈ {m;mA;⇓A} AC. hX→C; #0→#0i AD. h#0↔D;C↔ei When symbol BAor symbol eAappears in the string agent A5starts to work by consuming the symbol and replacing it by two symbols: ⇑Afor agent A6that moves right to set PM-colony agent Aas inactive and the second symbol for agent A1to continue computation. A5 a. he→Z;e→ei b. hZ↔BA;e→ei c. hZ↔eA;e→ei d. hBA→mB;e→⇑Ai e. heA→m;e→⇑Ai f. hmB↔Z;⇑A↔ei g. hm↔ Z;⇑A↔ei A6 I. he→B;e→ei II. hB↔⇑A;e↔Xi; X∈E∪ { bBc|b, c ∈E∪N∪ {#,#0}, B ∈N− {A}} III. hX↔B;⇑A↔ei IV. hB↔⇑A;e→bAci V. ⇑A→e;bAc→bAc V I. bAc↔B;e→e Phase 3. - Simulation of execution of the rules This phase starts with arrows change. Instead of ⇑and mthe agent A1uses and . The change is done by agent A1and A5. L. Ciencialov´a, L. Cienciala 107 A1 44.h⇑↔ C;e→ei 45.hC→;e→ei 46.h↔;e→ei A5 h. hZ↔#0;e↔⇑i i. h#0→#0;⇑→i j. h#0↔Z;↔ei The agent A1reads the string from the left to the right, it skips symbols from E∪N, changes bActo Aand sends messages to performing agent to add, move, rewrite or delete symbols. A1 47.h↔;e↔aia∈E∪N 48.↔;e→bAc 49.ha↔;↔ei 50.→;bAc→A 51.hA↔;↔ei 52.h↔;e→bAci Using the program 52 agent A1consumes symbol corresponding to active agent. For every rule of PM-colony there exists sets of programs of agent A1and one agent performing the action. If the rule is deletion of the form (a;Ai;b)→(ε;Ai;b),for a∈E∪N;b∈E∪N∪ {#}, (a;Ai;b)→(a;Ai;ε),for a∈E∪N∪ {#};b∈E∪N, the programs are following: A1 53.haAb→A;→Dxyi xy is La or Rb depending on which side the symbol have to be deleted 54.hA↔e;Dxy ↔i Adel A1.he→J;e→ei A2.hJ↔Dxy;e→ei; A3.hDLa →dLa;e↔i A4.hdLa ↔A;↔Ji A5.hA→A;J→J0i A6.hJ0↔dLa;A↔ei A7.hdLa ↔a0;e↔J0ia0is aif a∈Eor a0is daA A8.hJ0→J1;a0→ei A9.hJ1→J2;e↔dLai A10.hJ2→J;dLa →ei A11.hDRb →dRb;e↔i A12.h↔J;dRb ↔b0ib0is bif b∈Eor b0is Abd A13.hb0→e;J→J0i A14.hJ0→J1;e↔dRbi A15.hJ1→J;dRb →ei If the rule is insertion of the form (a;Ai;b)→(a;c;Ai;b),for a;b∈E∪N∪ {#};c∈E∪N, (a;Ai;b)→(a;Ai;c;b),for a;b∈E∪N∪ {#};c∈E∪N, the programs are following: 108 Two Notes on APCol Systems A1 55.haAb→A;→Ixyi xy is Lc or Rc depending on which side the symbol have to be inserted 56.hA↔e;Ixy ↔i Ains A1.he→J;e→Ki A2.hJ↔A;K↔ILci;A13.hJ↔IRc;K→ci; A3.ILc →I0 Lc;A→AA14.IRc →I0 Rc;c→c A4.I0 Lc ↔J;A↔KA15.c↔J;I0 Rc ↔e A5.J↔I0 Lc;K→cA16.J↔I0 Rc;e→ A6.I0 Lc →I1 Lc;c→cA17.I0 Rc →K;↔J A7.c↔J;I1 Lc ↔e A8.J↔I1 Lc;e↔A A9.I1 Lc →I2 Lc;A→A A10.A↔J;I2 Lc ↔e A11.J↔I2 Lc;e→ A12.I2 Lc →K;↔J If the rule is substitution of the form (a;Ai;b)→(c;Ai;b),for b∈E∪N∪ {#};a;c∈E, (a;Ai;b)→(a;Ai;c),for a∈E∪N∪ {#};b;c∈E, the programs are following: A1 57.haAb→A;→Sxyi xy is Lc or Rc depending on which side the symbol have to be replaced 58.hA↔e;Sxy ↔i Asubs A1.he→J;e→ei A2.hJ↔SLc;e→ei;A11.hJ↔SRc;e→ei; A3.hSLc →sLc;e→iA12.hSRc →sRc;e→ci A4.hsLc ↔A;↔JiA13.hc↔J;sRc ↔bi A5.hA→A;J→J0iA14.J→J0;b→ A6.hJ0↔a;A↔sLciA15.J0→J1;↔sRc A7.sLc →s0 Lc;a→cA16.J1→J;sRc →e A8.s0 Lc ↔J0;c↔e A9.J0→J1;e↔s0 Lc A10.J1→J;s0 Lc →e If the rule is move of the form (a;Ai;b)→(Ai;a;b),for a∈E∪N;b∈E∪N∪ {#}, (a;Ai;b)→(a;b;Ai),for a∈E∪N∪ {#};b∈E∪N, the programs are following: A1 59.haAb→A;→Mxyi xy is LA or RA depending on which side the symbol have to be moved 60.hA↔e;Mxy ↔i L. Ciencialov´a, L. Cienciala 109 Amov A1.he→J;e→ei A2.hJ↔MLA;e→ei;A10.hJ↔MRA;e→ei; A3.hMLA →mLA;e→iA11.hMRA →mRA;e→ei A4.hmLA ↔A;↔JiA12.he↔J;mRA ↔b0ib0is bif b∈Eor b0is Abd A5.hA→A;J→J0iA13.J→J0;b0→OOis bif b∈Eor Ois B A6.hA↔a;J0↔mLAiA14.hO↔A;J0↔mRAi A7.mLA →m0 LA;a→aA15.hA→A;mRA →i A8.a↔J0;m0 LA →eA16.hA↔e;↔J0i A9.J0→J;e→eA17.hJ0→J;e→ei If the rule is death of the form (a;Ai;b)→(a;ε;b),for a;b∈E∪N∪ {#} the programs are following: A1 61.haAb→e;↔i In the last phase agent A1detects that the whole string is rewritten and it is time to non-deterministically choose if computation will be halted or will continue by simulating of following derivation step. A1 62.h↔;e↔#i 63.h→U; # ↔i 64.hU→V;→↓i 65.hU→F;→Fi 66.hV↔#0;↓↔ ei 67.h#0↔V;e→↑i 68.hV→e;↑→↑i The computation of the APCol system can halt only when in corresponding state of the PM-colony there is no applicable rule or in the case that program 56. is executed. 4 Boolean Circuits and APCol Systems In this part, we show how APCol systems can simulate the functioning of logic gates. The input is always inserted into the string. Because there is no inner structure in the APCol systems, we use direct addressing. It means that every input symbol obtains index determining which agent will consume it. The result will be find on the string at the end of computation. Theorem 2. The functioning of logic gates NOT, OR and AND can be simulated by APCol systems with only one agent. Proof. The first we show how APCol system for logic gate NOT is constructed. Let NOT gate has an input with index i. We can simulate NOT gate with only one agent with following restricted programs: 110 Two Notes on APCol Systems 1.he↔0i;e→1outi3.he↔1i;e→0outi 2.h0i→e; 1out ↔ei4.h1i→e; 0out ↔ei Formally, we define APCol system ΠNOT = (O, e, ANOT ), where O={e, 1i,0i,1out,0out}, ANOT = (ee, PAND), the set of programs is described above and initial string is formed from only one symbol 1ior 0i. The result is obtained after computation halts and it is placed in the string. Simulation of the AND gate is done by APCol system with only one agent and following programs: 5.he↔0i;e↔0ii6.he↔1i;e↔0ii7.he↔1i;e↔0ii 8.he↔1i;e↔1ii9.h0i→0out; 0i→ei10.h1i→0out; 0i→ei 11.h1i→1out; 1i→ei These programs can work only for boolean circuit with only one gate, because we expect that symbols of input are neighbouring. If we change the programs in such a way that they contains at most one communication rule. In this case they do not use context (one agent changes only one symbol on the string in one step). 12.he↔0i;e→ei13.he↔1i;e→ei14.he↔0i; 0i→0i 15.he↔1i; 1i→1i16.he↔1i; 0i→0i17.he↔0i; 1i→1i 18.h0i→0out; 0 →ei19.h1i→1out; 1 →ei20.h1i→0out; 0 →ei 21.h0i→0out; 1 →ei22.h0out ↔e;e→ei23.h1out ↔e;e→ei Formally, we define APCol system ΠAND = (O, e, AAND), where O={e, 1i,0i,1out,0out}, AAND = (ee, PAND), the set of programs is formed from programs 12.-23. and initial string contains only one symbol 1ior 0i. The result is obtained after computation halts and it is placed in the string. Simulation of the OR gate is done with programs very similar to programs of agent simulating AND gate. It is done by APCol system with only one agent and following programs: 24.he↔0i;e→ei25.he↔1i;e→ei26.he↔0i; 0i→0i 27.he↔1i; 1i→1i28.he↔1i; 0i→0i29.he↔0i; 1i→1i 30.h0i→0out; 0 →ei31.h1i→1out; 1 →ei32.h1i→1out; 0 →ei 33.h0i→1out; 1 →ei34.h0out ↔e;e→ei35.h1out ↔e;e→ei Formally, we define APCol system ΠOR = (O, e, AOR), where O={e, 1i,0i,1out,0out}, AOR = (ee, PAND), the set of programs is formed from programs 24.-35. and initial string contains only one symbol 1ior 0i. The result is also obtained after computation halts and it is placed in the string. We can proceed to formulate a Boolean circuit simulation theorem: Theorem 3. For every Boolean circuit there exists an APCol system that can simulate its functioning and for input string formed from input signals of Boolean circuit APCol system generates correct output. Let α= (V, E, λ) be a boolean circuit. We associate with each gate a label from a set {1,...,|V|}. Let (x1, . . . , xp) be the vector of input signals for the boolean circuit. The correspoding initial string of APCol system is formed from objects x0j; 1 ≤j≤p. For simulation of the whole boolean circuit, we cannot only put the corresponding agents together. The output of one agent can be the input for L. Ciencialov´a, L. Cienciala 111 more agents. To obtain more input symbols we modify input objects consumed by agents (we use X0 iinstead of Xi), output objects are in a form Xi– output from the agent i. We also add one more agent generating inputs for those agents which are connected with output of i-th agent. We deal with three cases: i-th agent is connected with one agent, with two agents or with magents, m > 2. Let ybe the index of agent with output and zifor 1 ≤i≤mare indices of agents with input connected to agent yor corresponding to the initial input; X∈ {0,1}. We construct programs for agent A|V|+1 = (ee, P|V|+1) generating inputs. Programs for three variants of generated number of inputs One input Two inputs 36.he↔Xy;e→X0 z1i38.he↔Xy;e→X0 z1i 37.hX0 z1↔e;Xy→ei39.hX0 z1↔e;Xy→X0 z2i 40.hX0 z2↔e;e→ei minputs; m > 2 41.he↔Xy;e→X0 z1i 42.hX0 z1↔e;Xy→X2yi 43.he→X0 z2;X2y→X2yi 44.hX0 z2↔e;X2y→X3yi 45.he→X0 zk;Xky →Xkyifor 2 < k ≤m 46.X0 zk ↔e;Xky →X(k+1)yfor 2 < k ≤m−1 47.hX0 zm ↔e;Xmy →ei The agents associated to logic gates can consume only input symbols of a type X0 i, where Xis 0 or 1 and iis label of gate. At the beginning of computation there are only symbols of type Xipresent in the input string of APCol system. The only agent with applicable program is agent A|V|+1 – program 36., 38. or 41. In the next step agent A|V|+1 put the first input symbol (X0 zk), where zk is label of corresponding gate. From this step agents associated with gates started to do their work – rewriting their own inputs into outputs – and agent A|V|+1 is rewriting their output to inputs. If the boolean circuit is defined correctly, at the end of computation there are only symbols X0 out in the string corresponding to the output of boolean circuit. 5 Conclusion In this paper we continue with our research devoted to relationship of APCol systems which are devices derived from P colonies and P systems in general with classical formal models used not only in theoretical computer science. For this paper we have chosen PM-colonies and boolean circuits. We showed that APcol systems with two agents can simulate PM-colonies with strict conflict solving. In the second part we showed that even APCol systems are without inner structure they can substitute boolean circuits. 118 A. Leporati et al. M h0 h1 h2 h3 ab a c 0110 q 0110 q h0 h1 h2 h3 M Fig. 1. The (empty) membrane structure of a P system is embedded into another P system simulating a Turing machine M. family Π={Πx:x∈Σ?}of P systems, where input strings of the same length n are associated to P systems sharing the same membrane structure and rules Π(n), which only differ with respect to the initial multisets they contain. Then, multiple empty membrane structures Π(0), Π(1), . . . , Π(m) can be embedded, up to the maximum possible query string length (an upper bound is given, for instance, by the length of the tape of M), and the correct one is selected at runtime by the P system simulating M(Fig. 3). When the simulated Turing machine performs multiple queries with query strings of the same length during its computation, it is possible to embed multiple copies of each P system Π(n) [24]. Each of these copies can then be used for a single query (Fig. 4). A possible alternative is to reset the configuration of P system Π(n) after the query simulation has been performed [12]. 2.1 Subroutines in Tissue P Systems The oracle query construction for cell-like P systems embeds elements of a family of P systems into a membrane where a Turing machine is simulated. This construc- Subroutines in P Systems and Closure Properties 119 h0 h1 h2 h3 M 0110 q $$ ah0bh0 ah3 ch2 h0 h1 h2 h3 M 0110 q $$ ah0bh0 ah3 ch2 h0 h1 h2 h3 M 0110 q $$ ab a c h0 h1 h2 h3 M 0110 q $$ h0 h1 h2 M 0110 q $$ h1 h2 a b b c yes h0 h1 h2 M h1 h2 a b b 0110 qyes $$ Fig. 2. The query string xon the tape of the simulated Turing machine is encoded as the initial configuration of the embedded P system Πx. Each object is subscripted by the label of its target membrane, which it reaches by using send-in rules. When all objects have reached their destination, they simultaneously lose the subscripts, and the computation of Πxbegins. The output of Πxis then read and incorporated into the state of the simulated Turing machine, as in the configuration following the query. 120 A. Leporati et al. M 0110 q $$ Π(0) Π(1) Π(2) Π(3) Π(4) v M Π(0) Π(1) Π(2) Π(3) Π(4) w 10 q $$ Fig. 3. Query strings of different lengths can be processed by distinct embedded P systems, selected when the oracle query is simulated. M M 01$ q $11$ q $ Π(0)1Π(0)2Π(0)3 Π(1)1Π(1)2Π(1)3 Π(2)1Π(2)2Π(2)3 Π(0)1Π(0)2Π(0)3 Π(1)1Π(1)2Π(1)3 Π(2)1Π(2)2Π(2)3 vw Fig. 4. Multiple query strings of the same length can be processed by replicating the P systems simulating the oracle and using each of them only once. tion can be adapted to tissue P systems by having the Turing machine simulation take place in a cell, and placing the elements of the family of tissue P systems deciding the oracle language on the side [16]. The communication needed in order to simulate the oracle queries in this variant is not hierarchical, but between adjacent cells (Fig. 5). Subroutines in P Systems and Closure Properties 121 M 0110 q $$ Π(3) Π(4) Π(3) Π(4) Π(4) v M Π(3) Π(4) Π(3) Π(4) Π(4) w 1100 q $$ Fig. 5. Simulating oracle queries in tissue P systems. 3 Subroutines in Monodirectional Cell-like P Systems In monodirectional cell-like P systems [13, 14], where send-in rules are disallowed, the construction of Section 2 does not apply. However, we can turn the construction of Fig. 1 inside out, by having the Turing machine simulation embedded into the input membrane of the P system Πsimulating the oracle (Fig. 6). Instead of sending in the encoding of the query string, it is the encoding of the configuration of the Turing machine that is sent out, through the whole membrane structure of Π, where it waits for the oracle query result (Fig. 7) [13, 14]. This is needed because the P system simulating the oracle can only send its result outwards and, since the system is monodirectional, the only way to intercept it is to move out the entire simulation of the Turing machine. Unlike the bidirectional case, the objects of the initial configuration of Πcannot be arranged during the query simulation, as that requires send-in if the membrane structure of Πis not linear or if the input membrane is not elementary. A solution is to have them already in their correct position in the initial configuration of the combined P system but with a timer subscript, which is deleted at a predefined time step t, when a query may take place. If the simulated Turing machine does not perform a query at time t, it can be adapted so that it makes a “dummy” query at that time, ignoring its result. As in the bidirectional case, the oracle strings are usually only available at runtime, and thus multiple P systems simulating oracles must be arranged in advance, in order to accommodate any possible query string. Given the restriction on the direction of communication, a natural solution is to nest these auxiliary P systems, placing each one inside the input membrane of the next one. When a query takes place, the Turing machine configuration is first moved to the first P system suitable for the query string, where the multiset encoding it is left; 122 A. Leporati et al. M h0 h1 h2 h3 ab at c 0110 q 0110 q h0 h1 h2 h3 h at bt a Fig. 6. In the monodirectional case, the P system simulating the Turing machine is embedded into the input membrane of the P system Πsimulating the oracle; the other objects in the initial configuration of Πhave an associated timer for synchronisation purposes. then, the Turing machine configuration is moved outside the whole set of auxiliary P systems, where it waits for the result of the query (Fig. 7). If multiple queries are carried out, it suffices to repeatedly nest the array of auxiliary P systems, always using the input membranes as junction points, and repeating the query procedure as many times as necessary (Fig. 8) [13, 14]. 4 Discussion and Open Problems Many complexity theory results for P systems have the form NP ⊆PMCD for some class Dof P systems, and by closure under complementation this implies NP ∪coNP ⊆PMCD[22]. Solving NP-complete problems usually requires some form of “context-sensitivity”, such as cooperative evolution rules (even minimal cooperation), membranes charges, membrane dissolution, or antimatter annihilation [31, 30, 20, 4, 5]. However, these same features typically suffice to carry Subroutines in P Systems and Closure Properties 123 as 0110 q h0 h1 h2 h3 h as bs cs 0110 q h0 h1 h2 h3 h a a b c 0110 qh h0 h1 h2 h1 h2 a b b c yes Fig. 7. Query simulation procedure for monodirectional cell-like P systems. 124 A. Leporati et al. 0110 q Π(0) Π(1) Π(2) Π(3) Π(4) 0110 q Π(0) Π(1) Π(2) Π(3) Π(4) Π(0) Π(1) Π(2) Π(3) Π(4) Π(0) Π(1) Π(2) Π(3) Π(4)                                    3rd query                                    2nd query                                    1st query Fig. 8. Repeated nesting of monodirectional cell-like P systems to perform queries of a priori unknown length (on the left) and for multiple queries of a priori unknown length (on the right). Subroutines in P Systems and Closure Properties 125 out the oracle simulation constructions described in Section 2 or 3, which imply that PMCDhas the form PCfor some class C. This means that it is quite unlikely that NP ∪coNP is an exact characterisation of PMCD. Indeed, if NP∪coNP were of the form PC, then PNP∪coNP =PPC. But PPC= PC: if L1∈PPC, there exists a Turing machine M1with oracle for L2∈PCsuch that L(M1) = L1, and a Turing machine M2with an oracle for L3∈Csuch that L2=L(M2). Let Mbe a Turing machine with oracle for L3. This machine simulates M1until it enters its query state, then it simulates M2until it enters its own query state; since Mand M2have the same oracle, the queries of M2can be answered directly. Then L(M) = L(M1) = L1, and we can conclude that PPC= PC. But then PNP∪coNP =PC=NP ∪coNP. Since PNP∪coNP =PNP, this class has complete problems, for instance the standard complete problem Hof deciding if a Turing machine Mwith NP oracle accepts a string xwithin tsteps (where t is given in unary notation). Then either H∈NP or H∈coNP, and it is hard for both NP and coNP; this means that either there exists a NP-hard problem in coNP, or a coNP-hard problem in NP: in both cases, this implies NP =coNP. Furthermore, it is often the case [24, 12, 14, 16] that the amount of contextsensitivity that allows us to simulate Turing machines with oracles also suffices, at least in the bidirectional case, to simulate not only oracles for decision problems, but their counting version, which is usually more powerful. For instance, several variants of P systems without non-elementary membrane division rules characterise the complexity class PPP (which coincides with P#P) [19, 11, 14, 16]. Finally, notice that the above remarks apply even to variants of P systems powerful enough to characterise PSPACE in polynomial time [27, 3, 28, 4], even if the algorithms developed in order to prove these results do not usually employ an oracle simulation construction. Indeed, the class PSPACE is closed under exponentiation: PPSPACE =PSPACE. The property investigated in this paper, closure under exponentiation, that is, satisfying PC=C, seems to apply to a wide range of variants of P systems. A natural follow-up question is whether the more common closure under oracles (or under subroutines), where C=CC, does also apply for some of these variants. This also requires establishing a notion of “P system with oracle”; a first definition has been already given in [12], albeit for purely technical reasons. An interesting open problem, although a presumably challenging one from a technical standpoint, is to formally characterise the membrane computing features (such as combination of rules or properties of the membrane structures) that enable the oracle simulation construction. References 1. Alhazov, A., Leporati, A., Mauri, G., Porreca, A.E., Zandron, C.: The computational power of exponential-space P systems with active membranes. In: Mart´ınezdel-Amor, M.A., P˘aun, Gh., P´erez-Hurtado, I., Romero-Campero, F.J. (eds.) Pro- 126 A. Leporati et al. ceedings of the Tenth Brainstorming Week on Membrane Computing, vol. I, pp. 35–60. F´enix Editora (2012) 2. Alhazov, A., Leporati, A., Mauri, G., Porreca, A.E., Zandron, C.: Space complexity equivalence of P systems with active membranes and Turing machines. Theoretical Computer Science 529, 69–81 (2014) 3. Alhazov, A., Mart´ın-Vide, C., Pan, L.: Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes. Fundamenta Informaticae 58(2), 67–77 (2003) 4. Alhazov, A., P´erez-Jim´enez, M.J.: Uniform solution to QSAT using polarizationless active membranes. In: Durand-Lose, J., Margenstern, M. (eds.) Machines, Computations, and Universality, 5th International Conference, MCU 2007, Lecture Notes in Computer Science, vol. 4664, pp. 122–133. Springer (2007) 5. D´ıaz-Pernil, D., Alhazov, A., Freund, R., Guti´errez-Naranjo, M.A., Leporati, A.: Recognizer P systems with antimatter. Romanian Journal of Information Science and Technology 18(3), 201–217 (2015) 6. Gazdag, Z., Kolonits, G.: Remarks on the computational power of some restricted variants of P systems with active membranes. In: Leporati, A., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) Membrane Computing, 17th International Conference, CMC 2016. Lecture Notes in Computer Science, vol. 10105, pp. 209–232. Springer (2017) 7. Gazdag, Z., Kolonits, G., Guti´errez-Naranjo, M.A.: Simulating Turing machines with polarizationless P systems with active membranes. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Sos´ık, P., Zandron, C. (eds.) Membrane Computing, 15th International Conference, CMC 2014. Lecture Notes in Computer Science, vol. 8961, pp. 229–240 (2014) 8. Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Romero-Campero, F.J.: A uniform solution to SAT using membrane creation. Theoretical Computer Science 371(1–2), 54–61 (2007) 9. Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd Edition. Addison-Wesley (2006) 10. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: Constant-space P systems with active membranes. Fundamenta Informaticae 134(1–2), 111–128 (2014) 11. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: Simulating elementary active membranes, with an application to the P conjecture. In: Gheorghe, M., Rozenberg, G., Sos´ık, P., Zandron, C. (eds.) Membrane Computing, 15th International Conference, CMC 2014, Lecture Notes in Computer Science, vol. 8961, pp. 284–299. Springer (2014) 12. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: Membrane division, oracles, and the counting hierarchy. Fundamenta Informaticae 138(1–2), 97–111 (2015) 13. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: Monodirectional P systems. Natural Computing 15(4), 551–564 (2016) 14. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: The counting power of P systems with antimatter. Theoretical Computer Science (2017), in press 15. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C.: Shallow nonconfluent P systems. In: Leporati, A., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) Membrane Computing, 17th International Conference, CMC 2016. Lecture Notes in Computer Science, vol. 10105, pp. 307–316 (2017) Subroutines in P Systems and Closure Properties 127 16. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E.P., Zandron, C.: Characterising the complexity of tissue P systems with fission rules. Journal of Computer and System Sciences (2017), in press 17. Leporati, A., Mauri, G., Porreca, A.E., Zandron, C.: A gap in the space hierarchy of P systems with active membranes. Journal of Automata, Languages and Combinatorics 19(1–4), 173–184 (2014) 18. Murphy, N., Woods, D.: The computational power of membrane systems under tight uniformity conditions. Natural Computing 10(1), 613–632 (2011) 19. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1993) 20. P˘aun, Gh.: P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics 6(1), 75–90 (2001) 21. P´erez-Jim´enez, M.J.: The P versus NP problem from the membrane computing view. European Review 22(01), 18–33 (2014) 22. P´erez-Jim´enez, M.J., Romero-Jim´enez, A., Sancho-Caparrini, F.: Complexity classes in models of cellular computing with membranes. Natural Computing 2(3), 265–284 (2003) 23. P´erez-Jim´enez, M.J., Sos´ık, P.: An optimal frontier of the efficiency of tissue P systems with cell separation. Fundamenta Informaticae 138(1–2), 45–60 (2015) 24. Porreca, A.E., Leporati, A., Mauri, G., Zandron, C.: P systems simulating oracle computations. In: Gheorghe, M., P˘aun, Gh., Salomaa, A., Rozenberg, G., Verlan, S. (eds.) Membrane Computing, 12th International Conference, CMC 2011, Lecture Notes in Computer Science, vol. 7184, pp. 346–358. Springer (2012) 25. Porreca, A.E., Leporati, A., Mauri, G., Zandron, C.: Sublinear-space P systems with active membranes. In: Csuhaj-Varj´u, E., Gheorghe, M., Rozenberg, G., Salomaa, A., Vaszil, G. (eds.) Membrane Computing, 13th International Conference, CMC 2012, Lecture Notes in Computer Science, vol. 7762, pp. 342–357. Springer (2013) 26. Romero-Jim´enez, A., P´erez-Jim´ez, M.J.: Simulating Turing machines by P systems with external output. Fundamenta Informaticae 49(1–3), 273–287 (2002) 27. Sos´ık, P.: The computational power of cell division in P systems: Beating down parallel computers? Natural Computing 2(3), 287–298 (2003) 28. Sos´ık, P., Rodr´ıguez-Pat´on, A.: Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences 73(1), 137–152 (2007) 29. Stockmeyer, L.J.: The polynomial-time hierarchy. Theoretical Computer Science 3(1), 1–22 (1976) 30. Valencia-Cabrera, L., Orellana-Mart´ın, D., Mart´ınez-del-Amor, M.A., Riscos-N´u˜nez, A., P´erez-Jim´enez, M.J.: Computational efficiency of minimal cooperation and distribution in polarizationless P systems with active membranes. Fundamenta Informaticae 153(1–2), 147–172 (2017) 31. Valencia-Cabrera, L., Orellana-Mart´ın, D., Mart´ınez-del-Amor, M.A., Riscos-N´u˜nez, A., P´erez-Jim´enez, M.J.: Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation. Theoretical Computer Science (2017), in press 32. Valsecchi, A., Porreca, A.E., Leporati, A., Mauri, G., Zandron, C.: An efficient simulation of polynomial-space Turing machines by P systems with active membranes. In: P˘aun, Gh., P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, 10th International Workshop, WMC 2009, Lecture Notes in Computer Science, vol. 6501, pp. 461–478. Springer (2010) 134 L.F. Mac´ıas-Ramos et al. Definition 3. Arecognizer P system with symport/antiport rules and membrane division of degree q≥1is a tuple Π= (Γ, E, Σ, M1, . . . , Mq,R1,· · · ,Rq, iin, iout) where: •(Γ, E,M1, . . . , Mq,R1,··· ,Rq, iout)is a P system with symport/antiport rules and membrane division of degree q≥1, as defined in the previous section; •The working alphabet Γhas two distinguished objects yes and no, at least one copy of them present in some initial multisets M1, . . . , Mq, but none of them is present in E; •Σis an (input) alphabet strictly contained in Γsuch that E ∩ Σ=∅; • M1, . . . , Mqare multisets over Γ\Σ; •iin ∈ {1, . . . , q}is the input membrane; •The output region iout is the environment; •All computations halt; •If Cis a computation of Π, then either object yes or object no (but not both) must have been released into the output region (the environment), and only at the last step of the computation. Definition 4. Arecognizer P system with symport/antiport rules, membrane division and without environment of degree q≥1is a tuple Π= (Γ, E, Σ, M1,...,Mq,R1,· · · ,Rq, iin, iout) where: •(Γ, E, Σ, M1, . . . , Mq,R1,· · · ,Rq, iout)is a P system with symport/antiport rules and membrane division. •The working alphabet Γhas two distinguished objects yes and no, at least one copy of them present in some initial multisets M1, . . . , Mq, but none of them is present in E. • E =∅. •Σis an (input) alphabet strictly contained in Γsuch that E ∩ Σ=∅. • M1, . . . , Mqare multisets over Γ\Σ. •iin ∈ {1, . . . , q}is the input membrane. •iout ∈ {1, . . . , q}is the output membrane. •All computations halt. •If Cis a computation of Π, then either object yes or object no (but not both) must have been released into the output region, and only at the last step of the computation. For each multiset m∈ Mf(Σ), the computation of the system Πwith input m∈ Mf(Σ) starts from the configuration of the form (M1, . . . , Miin +m, . . . , Mq;∅), that is, the input multiset mhas been added to the contents of the input membrane iin, and we denote it by Π+m. Therefore, we have an initial configuration P Systems with Symport/Antiport and Membrane Division 135 associated with each input multiset m(over the input alphabet Σ) in this kind of systems. Given a recognizer P system with symport/antiport rules (with or without environment) and a halting computation C={Ct}t<r+1 of Π(r∈N), we define the result of Cas follows: Output(C) =        yes,if Ψ{yes,no}(Mr,iout ) = (1,0) ∧ Ψ{yes,no}(Mt,iout ) = (0,0) for t= 0, . . . , r −1 no,if Ψ{yes,no}(Mr,iout ) = (0,1) ∧ Ψ{yes,no}(Mt,iout ) = (0,0) for t= 0, . . . , r −1 where Ψis the Parikh mapping, and Mt,iout is the multiset over Γ\ E associated with the output region at the configuration Ct, in particular, Mr,iout is the multiset over Γ\ E associated with the output region at the halting configuration Cr. We say that a computation Cis an accepting computation (respectively, rejecting computation) if Output(C) = yes (resp., Output(C) = no), that is, if object yes (resp., object no) appears in the output region associated with the corresponding halting configuration of C, and neither object yes nor no appears in the output region associated with any non–halting configuration of C. Let us notice that if a recognizer P system Π= (Γ, E, Σ, M1, . . . , Mq,R1,· · · ,Rq, iin, iout) has a symport rule of the type (i, λ/u, 0) then alph(u)∩(Γ\ E)=∅, that is, the multiset umust contains some object from Γ\ E because on the contrary, all computations of Πwould be not halting. For each natural number k≥1, we denote by CDC(k) (respectively, CDS(k) or CDA(k)) the class of recognizer P systems with membrane division and with symport/antiport rules (resp., allowing only symport or antiport rules) of length at most k. In the case of P systems without environment, we denote by \ CDC(k) (\ CDS(k) or \ CDA(k) respectively) the class of recognizer P systems with membrane division without environment and with symport/antiport rules (allowing only symport or only antiport rules respectively) of length at most k. 4 Polynomial Complexity Classes of P Systems with Symport/Antiport In this section, we define what solving a decision problem in the framework of P systems with symport/antiport rules in a uniform and efficient way, means. Bearing in mind that they provide devices with a finite description, a numerable family of membrane systems will be necessary in order to solve a decision problem. Definition 5. We say that a decision problem X= (IX, θX)is solvable in a uniform way and polynomial time by a family Π={Π(n)|n∈N}of recognizer P systems with symport/antiport rules and membrane division (with or without environment) if the following holds: 136 L.F. Mac´ıas-Ramos et al. •The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(n)from n∈N. •There exists a pair (cod, s)of polynomial-time computable functions over IX such that: −for each instance u∈IX,s(u)is a natural number, and cod(u)is an input multiset of the system Π(s(u)); −for each n∈N,s−1(n)is a finite set; −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 Π(s(u)) with input cod(u)is halting and it performs at most p(|u|)steps; −the family Πis sound with regard to (X, cod, s), that is, for each u∈IX, if there exists an accepting computation of Π(s(u)) with input cod(u), then θX(u) = 1; −the family Πis complete with regard to (X, cod, s), that is, for each u∈IX, if θX(u)=1, then every computation of Π(s(u)) with input cod(u)is an accepting one. From the soundness and completeness conditions above we deduce that every P system Π(n) is confluent, in the following sense: every computation of a system with the same input multiset must always give the same answer. Let Rbe a class of recognizer P systems with symport/antiport rules. We denote by PMCRthe set of all decision problems which can be solved in a uniform way and polynomial time by means of families of systems from R. The class PMCRis closed under complement and polynomial–time reductions [9]. In what follows, we prove two technical results concerning recognizer P systems. Proposition 1. Let Π= (Γ, E, Σ, M1,...,Mq,R1,··· ,Rq, iin, iout)be a recognizer P systems with symport/antiport rules with length at most k,k≥2, and without membrane division. Let M=|M1+· · ·+Mq|and let C= (C0,C1, . . . , Cm) be a computation of ΠThen, |C∗ 0|=M, and for each t, 0≤t < m, we have |C∗ t+1| ≤ |C∗ t| · k, and |C∗ t+1| ≤ M·kt Proof: Obviously, |C∗ 0|=|C0(0) + C0(1) + · · · +C0(q)|=|M1+···+Mq|=M. Suppose 0 ≤t<m, and let us compute C∗ t+1 =Ct+1(0) + Ct+1(1) + · · · +Ct+1(q). Bearing in mind that only the skin membrane can send and receive objects from the environment, we have Ct+1(0) + Ct+1(2) + Ct+1(3) + ···+Ct+1(q)⊆ Ct(0) + Ct(1) + · · · +Ct(q) Next, let us see what objects membrane 1 can receive at step t+ 1. •On the one hand, membrane 1 can receive objects from Ct(0). •On the other hand, membrane 1 can receive objects from Eby means of rules in the skin membrane of the types: P Systems with Symport/Antiport and Membrane Division 137 – (a ei1. . . eir, in) with a∈ Ct(0) and ei1, . . . , eir∈ E,r≤k−1. – (a, out;ei1. . . eir, in) with a∈ Ct(1) and ei1, . . . , eir∈ E,r≤k−1. Then, |Ct+1(1)| ≤ |Ct(0) + Ct(1)| · (k−1). So, we have |C∗ t+1|=|Ct+1(0) + Ct+1(2) + Ct+1(3) + · · · +Ct+1(q)|+|Ct+1(1)| ≤ |Ct(0) + Ct(1) + · · · +Ct(q)|+|Ct(0) + Ct(1)| · (k−1) ≤ |C∗ t|+|C∗ t| · (k−1) ≤ |C∗ t| · k Finally, let us see that |C∗ t+1| ≤ M·ktby induction on t. For t= 1 the result is trivial because of |C∗ 1| ≤ (|C∗ 0|+M)·(k−1) = 2M·(k−1). Let tbe such that 1 < t < m and the result holds for t. Then, |C∗ t+1| ≤ |C∗ t| · kh.i ≤M·kt−1·k=M·kt  Proposition 2. Let Π={Π(n)|n∈N}a family of recognizer P systems from CDC(k), where k≥2, solving a decision problem X= (IX, θX)in polynomial time according to Definition 5. Let (cod, s)be a polynomial encoding associated with that solution. There exists a polynomial function r(n)such that for each instance u∈IX,2r(|u|)is an upper bound of the number of objects in all membranes of the system Π(s(u)) + cod(u)along any computation. Proof: Let p(n) be a polynomial function such that for each u∈IXevery computation of Π(s(u)) + cod(u) is halting and it performs at most p(|u|) steps. Let u∈IXbe an instance of Xand Π(s(u)) + cod(u) = (Γ, E, Σ, M1, . . . , Mq,R1, . . . , Rq, iin, iout) Let M=|M1+· · · +Mq|. Let C= (C0,C1, . . . , Cm), 0 ≤m≤p(|u|), be a computation of Π. First, let us suppose that we apply only communication rules at mconsecutive transition steps. From Proposition 1 we deduce that |C∗ 0|=Mand |C∗ t+1| ≤ M·kt, for each t, 0≤t < m. Thus, if we apply in a consecutive way the maximum possible number of communication rules (without applying any division rules) to the system Π(s(u)) + cod(u), in any instant of any computation of the system, M·kp(|u|)is an upper bound of the number of objects in the whole system. Now, let us consider the effect of applying in a consecutive way the maximum possible number of division rules (without applying any communication rules) to the system Π(s(u)) + cod(u) when the initial configuration has M·kp(|u|)objects. After that, an upper bound of the number of objects in the whole system by any computation is M·kp(|u|)·2p(|u|)·p(|u|). Then, we consider a polynomial function r(n) such that r(|u|)≥log(M) + p(|u|)·(1 + log k) + log(p(|u|)), for each instance u∈IX. The polynomial function r(n) fulfills the property required.  138 L.F. Mac´ıas-Ramos et al. Corollary 1. Let Π={Π(n)|n∈N}a family of recognizer P systems with symport/antiport rules and membrane division, solving a decision problem X= (IX, θX)in polynomial time according to Definition 5. Let (cod, s)a polynomial encoding associated with that solution. Then, there exists a polynomial function r(n)such that for each instance u∈IX,2r(|u|)is an upper bound of the number of objects from Ewhich are moved from the environment to all membranes of the system Π(s(u)) + cod(u)along any computation. Proof: It suffices to note that from Proposition 2 there exists a polynomial function r(n) such that for each instance u∈IX, 2r(|u|)is an upper bound of the number of objects in all membranes of the system Π(s(u)) + cod(u).  5 Simulating Systems from CDC(k) by Means of Systems from \ CDC(k) The goal of this section is to show that any P system with symport/antiport rules and membrane division can be simulated by a P system symport/antiport rules, membrane division and without environment, in an efficient way. First of all, we define the meaning of efficient simulations in the framework of recognizer P systems with symport/antiport rules. Definition 6. Let Πand Π′be recognizer P systems with symport/antiport rules. We say that Π′simulates Πin an efficient way if the following holds: 1. Π′can be constructed from Πby a deterministic Turing machine working in polynomial time. 2. There exists an injective function, f, from the set Comp(Π)of computations of Πonto the set Comp(Π′)of computations of Π′such that: ⋆There exists a deterministic Turing machine that constructs computation f(C)from computation Cin polynomial time. ⋆A computation C ∈ Comp(Π)is an accepting computation if and only if f(C)∈Comp(Π′)is an accepting one. ⋆There exists a polynomial function p(n)such that for each C ∈ Comp(Π) we have |f(C)| ≤ p(|C|). Now, for every family of recognizer P system with symport/antiport rules and membrane division solving a decision problem, we design a family of recognizer P systems with symport/antiport rules, membrane division and without environment efficiently simulating it, according to Definition 6. In what follows throughout this Section, let Π={Π(n)|n∈N}a family of recognizer P systems with symport/antiport rules and membrane division solving a decision problem X= (IX, θX) in polynomial time according to Definition 5, and let r(n) be a polynomial function such that for each instance u∈IX, 2r(|u|) is an upper bound of the number of objects from Ewhich are moved from the environment to all membranes of the system by any computation of Π(s(u)) + cod(u). P Systems with Symport/Antiport and Membrane Division 139 Definition 7. For each n∈N, let Π(n) = (Γ, E, Σ, µ, M1, . . . , Mq,R1, . . . , Rq, iin, iout) an element of the previous family Π, and for the sake of simplicity we denote rinstead of r(n)and 1is the label of the skin membrane. Let us consider the recognizer P system with symport/antiport rules of degree q1= 1 + q·(r+ 2) + |E|, with membrane division and without environment S(Π(n)) = (Γ′, Σ′, µ′,M′ 0,M′ 1, . . . , M′ q1,R′ 0,R′ 1, . . . , R′ q1, i′ in, i′ out) defined as follows: •Γ′=Γ∪ {αi: 0 ≤i≤r−1}. •Σ′=Σ. •Each membrane i∈ {1, . . . , q}of Πprovides a membrane of S(Π(n)) with the same label. In addition, S(Π(n)) has: ⋆ r+1 new membranes, labelled by (i, 0),(i, 1), . . . , (i, r), respectively, for each i∈ {1, . . . , q}. ⋆A distinguished membrane labelled by 0. ⋆A new membrane, labelled by lb, for each b∈ E. •µ′is the rooted tree obtained from µas follows: ⋆Membrane 0is the root of µ′and it is the father of the root of µ. ⋆For each b∈ E, membrane 0is the father of membrane lb. ⋆We consider a linear structure whose nodes are (i, 0),(i, 1), . . . , (i, r)and such that (i, j)is the father of (i, j −1), for each 1≤i≤qand 1≤j≤r. ⋆For each membrane iof µwe add the previous linear structure being membrane ithe father of membrane (i, r). •Initial multisets: M′ 0=∅,M′ lb={α0}, for each b∈ E, and (1 ≤i≤q)            M′ (i,0) =Mi M′ (i,1) =∅ . . . . . . M′ (i,r)=∅ M′ i=∅ •Set of rules: R′ 0∪ R′1∪ · · · ∪ R′q∪ {R′ (i,j): 1 ≤i≤q, 0≤j≤r} ∪ {R′ lb:b∈ E} where R′ 0=∅,R′ i=Rifor 1≤i≤q, and R′ (i,j)={(a, out;λ, in) : a∈Γ},for 1≤i≤q∧0≤j≤r} R′ lb={[αj]lb→[αj+1]lb[αj+1]lb: 0 ≤j≤r−2} ∪ {[αr−1]lb→[b]lb[b]lb,(lb, out;λ, in)},for b∈ E •i′ in = (iin,0),and i′ out = 0. 140 L.F. Mac´ıas-Ramos et al. Let us notice that S(Π(n)) can be considered as an extension of Π(n) without environment, in the following sense: ⋆ Γ ⊆Γ′, Σ ⊆Σ′and E=∅. ⋆Each membrane in Πis also a membrane in S(Π(n)). ⋆There is a distinguished membrane in S(Π(n)) labelled by 0 which plays the role of environment of Π(n). ⋆ µ is a subtree of µ′. ⋆R ⊆ R′, and now 0 is the label of a “ordinary membrane” in S(Π(n)). Next, we analyze the structure of the computations of system S(Π(n)) and we compare them with the computations of Π(n). Lemma 1. Let C′= (C′ 0,C′ 1, . . . )be a computation of S(Π(n)). For each t(1 ≤ t≤r)the following holds: • C′ t(i) = ∅, for 0≤i≤q. •For each 1≤i≤q, and 0≤j≤rwe have: C′ t(i, j) = {Mi,if j=t ∅,if j=t •For each b∈ E, there exist 2tmembranes labelled by lbwhose father is membrane 0and their content is: C′ t(lb) = {{αt},if 1≤t≤r−1 {b},if t=r Proof: By induction on t. Let us start with the basic case t= 1. The initial configuration of system S(Π(n)) is the following: • C′ 0(i) = ∅, for 0 ≤i≤q. •For each 1 ≤i≤qwe have C′ 0(i, 0) = Mi, and C′ 0(i, j) = ∅, for 1 ≤j≤r. •For each b∈ E, there exists only one membrane labelled by lbwhose contents is {α0}. At configuration C′ 0, only the following rules are applicable: •[α0]lb→[α1]lb[α1]lb, for each b∈ E. •(a, out;λ, in)∈ R(i,0), for each a∈supp(Mi). Thus, (a) For each i(1 ≤i≤q) we have:            C′ 1(i) = ∅ C′ 1(0) = ∅ C′ 1(i, 0) = ∅ C′ 1(i, 1) = Mi C′ 1(i, j) = ∅,for 2 ≤j≤r P Systems with Symport/Antiport and Membrane Division 141 (b) For each b∈ E, there are 2 membranes labelled by lbwhose father is membrane 0 and their content is {α1}. Hence, the result holds for t= 1. By induction hypothesis, let tbe such that 1 ≤t < r, and let us suppose the result holds for t, that is, • C′ t(i) = ∅, for 0 ≤i≤q. •For each 1 ≤i≤q, and 0 ≤j≤rwe have: C′ t(i, j) = {Mi,if j=t ∅,if j=t •For each b∈ E, there exist 2tmembranes labelled by lbwhose father is membrane 0 and their content is C′ t(lb) = {αt}(because t≤r−1). Then, at configuration C′ tonly the following rules are applicable: (1) If t≤r−2, the rules [αt]lb→[αt+1]lb[αt+1]lb, for each b∈ E. (2) If t=r−1, the rules [αt]lb→[b]lb[b]lb, for each b∈ E. (3) (a, out;λ, in)∈ R(i,t), for each a∈supp(Mi). From the application of rules of types (1) or (2) at configuration C′ t, we deduce that there are 2t+1 membranes labelled by lbin C′ t+1, for each b∈ E, whose father is membrane 0 and their content is {αt+1}, if t≤r−2, or {b}, if t=r−1. From the application of rules of type (3) at configuration C′ t, we deduce that C′ t+1(i, j) = {Mi,if j=t+ 1 ∅,if 0 ≤j≤r∧j=t+ 1 Bearing in mind that no other rule of system S(Π(n)) is applicable, we deduce that C′ t+1(i) = ∅, for 0 ≤i≤q. This completes the proof of this Lemma.  Lemma 2. Let C′= (C′ 0,C′ 1, . . . )be a computation of the P system S(Π(n)). Configuration C′ r+1 is the following: (1) C′ r+1(0) = b2r 1. . . b2r α, where E={b1, . . . , bα}. (2) C′ r+1(i) = Mi=C0(i), for 1≤i≤q. (3) C′ r+1(i, j) = ∅, for 1≤i≤q,0≤j≤r. (4) For each b∈ E, there exist 2rmembranes labelled by lbwhose father is membrane 0and their content is empty. Proof: From Lemma 1, the configuration C′ ris the following: • C′ r(i) = ∅, for 0 ≤i≤q. •For each i(1 ≤i≤q) we have C′ r(i, j) = {Mi,if j=r ∅,if j=r 142 L.F. Mac´ıas-Ramos et al. •For each b∈ E, there exist 2rmembranes labelled by lbwhose father is membrane 0 and their content is {b}. At configuration C′ ronly the following rules are applicables: •(a, out;λ, in)∈ R(i,r), for each a∈Γ∩supp(Mi). •(b, out;λ, in)∈ Rlb, for each b∈ E. Thus, • C′ r+1(0) = b2r 1. . . b2r α, where E={b1, . . . , bα}. • C′ r+1(i) = Mi=C0(i), for 1 ≤i≤q. • C′ r+1(i, j) = ∅, for 1 ≤i≤qand 0 ≤j≤r. •For each b∈ E, there exist 2rmembranes labelled by lbwhose father is membrane 0 and their content is empty.  Definition 8. Let C= (C0,C1, . . . , Cm)be a halting computation of Π(n). Then we define the computation S(C) = (C′ 0,C′ 1, . . . , C′ r,C′ r+1, . . . , C′ r+1+m)of S(Π(n)) as follows: (1) The initial configuration is:        C′ 0(i) = ∅,for 0≤i≤q C′ 0(i, 0) = C0(i),for 1≤i≤q C′ 0(i, j) = ∅,for 1≤i≤qand 1≤j≤r C′ 0(lb) = α0,for each b∈ E (2) The configuration C′ t, for 1≤t≤r, is described by Lemma 1. (3) The configuration C′ r+1 is described by Lemma 2. (4) The configuration C′ r+1+s, for 0≤s≤m, coincides with the configuration Cs of Π, that is, Cs(i) = C′ r+1+s(i), for 1≤i≤q. The content of the remaining membranes (excluding membrane 0) at configuration C′ r+1+sis equal to the content of that membrane at configuration C′ r+1, that is, these membranes do not evolve after step r+ 1. That is, every computation Cof Π(n) can be “reproduced” by a computation S(C) of S(Π(n)) with a delay: from step r+ 1 to step r+1+m, the computation S(C) restricted to membranes 1, . . . , q provides the computation Cof Π(n). From Lemma 1 and Lemma 2 we deduce the following: (a) S(C) is a computation of S(Π(n)). (b) Sis an injective function from Comp(Π(n)) onto Comp(S(Π(n))). Proposition 3. The P system S(Π(n)) defined in Definition 7 simulates Π(n)in an efficient way. Proof. In order to show that S(Π(n)) can be constructed from Π(n) by a deterministic Turing machine working in polynomial time, it is enough to note that the amount of resources needed to construct S(Π(n)) from Π(n) is polynomial in the size of the initial resources of Π(n). Indeed, P Systems with Symport/Antiport and Membrane Division 143 1. The size of the alphabet of S(Π(n)) is |Γ′|=|Γ|+r. 2. The initial number of membranes of S(Π(n)) is 1 + q·(r+ 2) + |E|. 3. The initial number of objects of S(Π(n)) is the initial number of objects of Π(n) plus |E|. 4. The number of rules of S(Π(n)) is |R′|=|R| + (r+ 1) · |E| +|Γ| · q·(r+ 1). 5. The maximal length of a communication rule of S(Π(n)) is equal to the maximal length of a communication rule of Π(n). From Lemma 1 and Lemma 2 we deduce that: (a) Every computation C′of S(Π(n)) has associated a computation Cof Π(n) such that S(C) = C′in a natural way. (b) The function Sis injective. (c) A computation Cof Π(n) is an accepting computation if and only if S(C) is an accepting computation of S(Π(n)). Finally, let us notice that if Cis a computation of Π(n) with length m, then S(C) is a computation of S(Π(n)) with length r+1+m. 6 Computational Complexity Classes of P Systems with Membrane Division and Without Environment In this Section, we analyze the role of the environment in the efficiency of P systems with membrane division. That is, we study the ability of these P systems with respect to the computational efficiency when the alphabet of the environment is an empty set. Theorem 1. For each k∈Nwe have PMCCDC(k+1) =PMC\ CDC(k+1). Proof: Let us recall that PMCCDC(1) =P(see [4] for details). Then, P⊆PMC\ CDC(1) ⊆PMCCDC(1) =P Thus, the result holds for k= 0. Let us show the result holds for k≥1. Since \ CDC(k+ 1) ⊆CDC(k+ 1) it suffices to prove that PMCCDC(k+1) ⊆ PMC\ CDC(k+1). For that, let X∈PMCCDC(k+1). Let {Π(n)|n∈N}be a family of P systems from CDC(k+ 1) solving X according to Definition 5. Let (cod, s) be a polinomial encoding associated with that solution. Let u∈IXbe an instance of the problem Xthat will be processed by the system Π(s(u))+cod(u). According to Proposition 2, let r(n) be a polynomial function that 2r(|u|)is an upper bound of the number of objects from Ewhich are moved from the environment to all membranes of the system by any computation of Π(s(u)) + cod(u)=(Γ, E, Σ, M1, . . . , Miin +cod(u), . . . , Mq,R, iin, iout) 246 L. Valencia-Cabrera et al. can be possible that some cjare missing, that is, that for some j, 1 ≤j≤p,cj does not appear in any membrane labelled by 1 in C2n+4np. Let e jbe the index j10 of that clause. It is going to take 2psteps. Proposition 6. Let C= (C0,C1,...,Cq)be a computation of the system Π(s(ϕ)) with input multiset cod(ϕ). (a0)For each 2k+ 1 (0≤k≤p−1) at configuration C2n+4np+2k+1 we have the following: -C2n+4np+2k+1(0) = {α2n+4np+2k+1, β2n+4np+2k+1} - There are 2nmembranes labelled by 1 such that each of them contains ?an object γ2n+4np or de j−1(respectively, an object dk) if the corresponding truth assignment does not make true (resp., makes true) the clause C1or Cj(2≤j≤p) (resp., the first kclauses); and ? mj−1objects cjfor 1≤j≤min(e j, k + 1) and mjobjects cjfor min(e j, k + 2) ≤j≤p. - There are 2nmembranes labelled by 2 such that each of them contains an object dk+1 if and only if the truth assignment associated to the branch makes true the first k+ 1 clauses. (a1)For each 2k(1≤k≤p−1) at configuration C2n+4np+2kwe have the following: -C2n+4np+2k(0) = {α2n+4np+2k, β2n+4np+2k} - There are 2nmembranes labelled by 1 such that each of them contains ?an object γ2n+4np or de j−1if the corresponding truth assignment does not make true the clause C1or Cj(2≤j≤p); and ? mj−1objects cjfor 1≤j≤min(e j, k)and mjobjects cjfor min(e j, k+ 1) ≤j≤p. - There are 2nempty membranes labelled by 2. (b)C2n+4np+2p(0) = {α2n+4np+2p, β2n+4np+2p}, and in C2n+4np+2pthere are 2n membranes labelled by 1, such that each of them contains an object dpif and only if the corresponding truth assignment makes true the input formula ϕ (de j−1otherwise), mj−1objects cjfor 1≤j≤min(e j, p + 1) and mjobjects cjfor min(e j, p + 1) ≤j≤p; and 2nempty membranes labelled by 2. Proof. (a) is going to be demonstrated by induction on k - The base case k= 1 is trivial because: (a0) at configuration C2n+4np we have: C2n+4np(0) = {α2n+4np, β2n+4np}and there exist 2nmembranes labelled by 1 containing an object γ2n+4np and mobjects cj(1 ≤j≤p); and there exist 2nempty membranes labelled by 2. Then, configuration C2n+4np yields configuration C2n+4np+1 by applying the rules: [α2n+4np →α2n+4np+1 ]0 [β2n+4np →β2n+4np+1 ]0 γ4np+2nc1[ ]2−→ [d1]2 10 If e jis not defined, we are going to suposse that it is equal to p+ 1. P Systems with Active Membranes: Minimal Cooperation Only Inwards 247 (a1) at C2n+4np+1(0) = {α2n+4np+1, β2n+4np+1}and there exist 2nmembranes labelled by 1 containing an object γ2n+4np if and only if there were no objects c1at configuration C2n+4np,m1−1 (respectively, m1) objects c1 if there was any object cjin this membrane in the previous configuration (resp., m1) and mjobjects cjfor 2 ≤j≤p; and 2nmembranes labelled by 2 containing an object d1if and only if there was at least one object c1within membrane labelled by 1 at configuration C2n+4np. Then, the configuration C2n+4np+1 yields configuration C2n+4np+2 by applying the rules: [α2n+4np+1 →α2n+4np+2 ]0 [β2n+4np+1 →β2n+4np+2 ]0 [d1]2−→ d1[ ]2 Thus, C2n+4np+2(0) = {α2n+4np+2, β2n+4np+2}, and there exist 2nmem- branes labelled by 1 containing an object d1(respectively, γ2n+4np) if the corresponding truth assignment makes true (resp., doesn’t make true) clause C1,m1−1 (resp., m1) objects c1and mjobjects cjfor 1 ≤j≤p; and there exist 2nempty membranes labelled by 2. Hence, the result holds for k= 1. - Supposing, by induction, result is true for k(0 ≤k≤p−1) -C2n+4np+2k(0) = {α2n+4np+2k, β2n+4np+2k} - In C2n+4np+2kthere are 2nmembranes labelled by 1 such that each of them contains ?an object γ2n+4np or de j−1(respectively, an object dk) if the corresponding truth assignment does not make true (resp., makes true) the clause C1or Cj(2 ≤j≤p) (resp., the first kclauses); and ? mj−1 objects cjfor 1 ≤j≤min(e j, k + 1) and mjobjects cjfor min(e j, k + 2) ≤j≤p. - In C2n+4np+2kthere are 2nempty membranes labelled by 2. Then, configuration C2n+4np+2kyields configuration C2n+4np+2k+1 by applying the rules: [α2n+4np+2k→α2n+4np+2k+1 ]0 [β2n+4np+2k→β2n+4np+2k+1 ]0 dkck+1[ ]2−→ [dk+1 ]2 Therefore, the following holds -C2n+4np+2k+1(0) = {α2n+4np+2k+1, β2n+4np+2k+1} - In C2n+4np+2k+1 there are 2nmembranes labelled by 1 such that each of them contains ?an object γ2n+4np or de j−1if the corresponding truth assignment does not make true the clause C1or Cj(2 ≤j≤p); and ? mj−1 objects cjfor 1 ≤j≤min(e j, k) and mjobjects cjfor min(e j, k + 1) ≤j≤p. - In C2n+4np+2k+1 there are 2nmembranes labelled by 2 such that each of them contains an object dk+1 if and only if the corresponding truth assignment makes true the first k+ 1 clauses. 248 L. Valencia-Cabrera et al. Then, configuration C2n+4np+2k+1 yields C2n+4np+2k+2 by applying the rules: [α2n+4np+2k+1 →α2n+4np+2k+2 ]0 [β2n+4np+2k+1 →β2n+4np+2k+2 ]0 [dk+1 ]2−→ dk+1 [ ]2 Therefore, the following holds -C2n+4np+2k+2(0) = {α2n+4np+2k+2, β2n+4np+2k+2} - In C2n+4np+2k+2 there are 2nmembranes labelled by 1 such that each of them contains ?an object γ2n+4np or de j−1(respectively, an object dk+1) if the corresponding truth assignment does not make true (resp., makes true) the clause C1or Cj(2 ≤j≤p) (resp., the first k+ 1 clauses); and ? mj−1 objects cjfor 1 ≤j≤min(e j, k + 2) and mjobjects cjfor min(e j, k + 3) ≤j≤p. - In C2n+4np+2k+2 there are 2nempty membranes labelled by 2. Hence, the result holds for k+ 1. - In order to prove (b) it is enough to notice that, on the one han, from (a) configuration C2n+4np+2p−1holds: -C2n+4np+2p−1(0) = {α2n+4np+2p−1, β2n+4np+2p−1} - In C2n+4np+2p−1there are 2nmembranes labelled by 1 such that each of them contains ?an object γ2n+4np or de j−1if the corresponding truth assignment does not make true the clause C1or Cj(2 ≤j≤p); and ? mj−1 objects cjfor 1 ≤j≤min(e j, p) and mjobjects cjfor min(e j, p+ 1) ≤j≤p. - In C2n+4np+2p−1there are 2nmembranes labelled by 2 such that each of them contains an object dpif and only if the corresponding truth assignment makes true the input formula ϕ. Then, configuration C2n+4np+2p−1yields configuration C2n+4np+2pby applying the rules: [α2n+4np+2p−1→α2n+4np+2p]0 [β2n+4np+2p−1→β2n+4np+2p]0 [dp]2−→ dp[ ]2 Then, we have C2n+4np+2p(0) = {α2n+4np+2p, β2n+4np+2p}, and there exist 2nmembranes labelled by 1 containing an object γ2n+4np or de j−1(respectively, an object dp) if the corresponding truth assignment does not make true (resp., makes true) the clause C1or Cj(2 ≤j≤p) (resp., the input formula ϕ), mj−1 objects cjfor 1 ≤j≤min(e j, p + 1) and mjobjects cj for min(e j, p + 1) ≤j≤p; and there exist 2nempty membranes labelled by 2.  P Systems with Active Membranes: Minimal Cooperation Only Inwards 249 5.4 Output stage The output phase starts at the (2n+ 4np + 2p)-th step, and takes exactly four steps when there is an affirmative answer and five steps when there is a negative one. Rules from 5.7 are devoted to compute this stage. -Affirmative answer: In this case, at configuration C2n+4np+2p, in some membrane 1 there is an object dp. By applying the rule [ dp]1−→ dp[ ]1(at the same time that [ α2n+4np+2p→α2n+4np+2p+1 ]0and [ β2n+4np+2p→ β2n+4np+2p+1 ]0are executed), an object dpis produced in membrane 0. Then by applying the rules α4np+2n+2p+1 dp[ ]1−→ [yes ]1and [ β2n+4np+2p+1 → β2n+4np+2p+2 ]0, an object yes is produced in some membrane labelled by 1 (only in one such membrane). At the next step, an object yes will appear at membrane labelled by 0 of the configuration C2n+4np+2p+3 by the application of the rule [ yes ]1−→ yes[ ]1. Let us note that object β2n+4np+2p+2 cannot interact with any object α. Finally, at computation step 2n+ 4np + 2p+ 4 an object yes is released to environment by the application of the rule [yes ]0−→ yes[ ]0and the computation halts. -Negative answer: In this case, at configuration C2n+4np+2p, there are no membranes labelled by 1 that contains an object dp, so the only rules executed are [α2n+4np+2p→α2n+4np+2p+1 ]0and [ β2n+4np+2p→β2n+4np+2p+1 ]0. Rule [β2n+4np+2p+1 →β2n+4np+2p+2 ]0is executed in the next step. Thus, at configuration C2n+4np+2p+2 in membrane labelled by 0 we execute have a copy of object α2n+4np+2p+1 and a copy of object β2n+4np+2p+2. By applying the rule α4np+2n+2p+1 β4np+2n+2p+2[ ]1−→ [no ]1,an object no is produced in only one membrane labelled by 1 (nondeterministically chosen). At the next step, this object no will move into membrane labelled by 0 by the application of the rule [ no ]1−→ no[ ]1. Finally, at configuration C2n+4np+2p+5 an object no is released to the environment when rule [ no ]0−→ no[ ]0, and then the computation halts. 5.5 Result Theorem 1. SAT ∈PMCDAM0(+es,mcmpin,−d,+n). Proof. The family Πof P systems previously constructed verifies the following: (a) The family Πis polynomially uniform by Turing machines because for each n, p ∈N, the rules of Π(hn, pi) of the family are recursively defined from n, p ∈N, and the amount of resources needed to build an element of the family is of a polynomial order in nand p, as shown below: – Size of the alphabet: 15n2p2 2+6n2p+3n2+2np2+35np 2+8n+7p+9 ∈Θ(n2p2). – Initial number of membranes: 3 ∈Θ(1). – Initial number of objects in membranes: 3np +n+ 3 ∈Θ(np). – Number of rules: 15n2p2 2+ 8n2p+ 4n2+41np 2+ 5n+ 5p+ 11 ∈Θ(n2p2). 250 L. Valencia-Cabrera et al. – Maximal number of objects involved in any rule: 3 ∈Θ(1). (b) The family Πis polynomially bounded with regard to (SAT,cod, s): indeed for each instance ϕof the SAT problem, any computation of the system Π(s(ϕ)) with input multiset cod(ϕ) takes at most 2n+ 4np + 2p+ 5 computation steps. (e) The family Πis sound with regard to (SAT,cod, s): indeed for each instance ϕof the SAT problem, if the computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation, then ϕis satisfiable. (f) The family Πis complete with regard to (SAT,cod, s): indeed, for each instance ϕof the SAT problem such that ϕis satisfiable, any computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation. Therefore, the family Πof P systems previously constructed solves the SAT problem in polynomial time and in a uniform way. Corollary 1. NP ∪co −NP ⊆PMCDAM0(+es,mcmpin,−d,+n). Proof. It suffices to notice that SAT problem is a NP-complete problem, SAT ∈PMCDAM0(+es,mcmpin,−d,+n), and the complexity class PMCDAM0(+es,mcmpin,−d,+n)is closed under polynomial-time reduction and under complement. 6 Conclusions From a computational complexity point of view and assuming that P6=NP, dissolution rules play a crucial role in classical polarizationless P systems with active membranes where there is no cooperation, no changing labels neither priorities. In that framework, PSPACE-complete problems can be solved in polynomial time when dissolution rules and division for elementary and non-elementary membranes are permitted. However, dissolution rules and division rules for non-elementary membranes can be replaced by minimal cooperation (the left-hand side of the rules has at most two objects) and minimal production (the right-hand side of the rules has at most two objects) in object evolution rules in order to obtain the computational efficiency [11]. In this paper, the ingredient of minimal cooperation and minimal production in object evolution rules is replaced by minimal cooperation and minimal production in send-in communication rules but we have need to use division for non-elementary membranes. The new systems considered are able to efficiently solve computational hard problems even by considering simple object evolution rules, that is, these kind of rules only produce one object. An analogous result can be obtained if minimal cooperation and minimal production are considered only for send-out rules, instead of send-in rules ([12]). The case where only elementary division is allowed, while keeping the restriction that minimal cooperation and minimal production are used in communication rules of the same direction (only in or only out) remains as future work, as well as the case where division rules are replaced by separation rules. P Systems with Active Membranes: Minimal Cooperation Only Inwards 251 What about the class SAM0(+es, mcmpin,−d, +n)? That is, what happens if we revisit the framework studied in this paper but replacing division rules by separation rules? We can adapt the reasoning used in the proof of P=PMCSAM0 bmc(−d,−n)(see [10]), and we can prove that by using families of recognizer membrane systems belonging to this class, only problems in class P can be solved in polynomial time. Acknowledgements This work was partially supported by Grant numbers 61472328 and 61320106005 of the National Natural Science Foundation of China. References 1. A. Alhazov, L. Pan. Polarizationless P systems with active membranes. Grammars, 7(2004), 141-159. 2. A. Alhazov, L. Pan, Gh. P˘aun. Trading polarizations for labels in P systems with active membranes. Acta Informaticae,41, 2-3 (2004), 111-144. 3. T.H. Cormen, C.E. Leiserson, R.L. Rivest. An Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, 1994. 4. M.R. Garey, D.S. Johnson. Computers and Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. 5. M.A. Guti´errez–Naranjo, M.J. P´erez–Jim´enez, A. Riscos–N´u˜nez, F.J. Romero– Campero. On the power of dissolution in P systems with active membranes. In R. Freund, Gh. P˘aun, Gr. Rozenberg, A. Salomaa (eds.). Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers, Lecture Notes in Computer Science,3850 (2006), 224– 240. 6. Gh. P˘aun. P systems with active membranes: Attacking NP–complete problems, Journal of Automata, Languages and Combinatorics,6(2001), 75–90. A preliminary version in Centre for Discrete Mathematics and Theoretical Computer Science Research Reports Series, CDMTCS-102, May 1999. 7. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini. Complexity classes in models of cellular computing with membranes. Natural Computing,2, 3 (2003), 265–285. 8. P. Sos´ık, A. Rodr´ıguez-Pat´on. Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences,73 (2007), 137152. 9. L. Valencia-Cabrera, D. Orellana-Mart´ın, M.A. Mart´ınez-del-Amor, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez. Polarizationless P systems with active membranes: Computational complexity aspects. Journal of Automata, Languages and Combinatorics,21, 1-2 (2016), 107123 10. L. Valencia-Cabrera, D. Orellana-Mart´ın, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez. Minimal cooperation in polarizationless P systems with active membranes. In C. Graciani, Gh. P˘aun, D. Orellana-Martn, A. Riscos-Nez, L. Valencia-Cabrera (eds.) Proceedings of the Fourteenth Brainstorming Week on Membrane Computing, 1-5 February, 2016, Sevilla, Spain, F´enix Editora, pp. 327-356. 252 L. Valencia-Cabrera et al. 11. L. Valencia-Cabrera, D. Orellana-Mart´ın, M.A. Mart´ınez-del-Amor, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez. Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation. Theoretical Computer Science, in press, 2017. 12. L. Valencia-Cabrera, D. Orellana-Mart´ın, M.A. Mart´ınez-del-Amor, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez. Restricted polarizationless P systems with active membranes: minimal cooperation only outwards. In this volume, 2017 (manuscript). 13. C. Zandron, C. Ferretti, G. Mauri. Solving NP-complete problems using P systems. In I. Antoniou, C.S. Calude, M.J. Dinneen (eds.) Unconventional Models of Computation, UMC’2K, Springer, London, 2000, pp. 153-164. Restricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Outwards Luis Valencia-Cabrera, David Orellana-Mart´ın, Miguel ´ A. Mart´ınez-del-Amor, Agust´ın Riscos-N´u˜nez, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {lvalencia, dorellana, mdelamor, ariscosn, marper}@us.es Summary. Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P.P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally efficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class Pcan be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide efficient solutions to NP–complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational efficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted. Key words: Membrane Computing, polarizationless P systems with active membranes, cooperative rules, the Pversus NP problem, SAT problem. 254 L. Valencia-Cabrera et al. 1 Introduction Membrane Computing is an emergent branch of Natural Computing providing distributed parallel and non-deterministic computing models whose computational devices are called membrane systems having units processor called compartments. This computing paradigm is 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. Celllike membrane systems use the biological membranes arranged hierarchically, inspired from the structure of the cell. In Membrane Computing, some variants capture the fact that membranes are not at all passive from a biochemistry view, for instance, the passing of a chemical compound through a membrane is often done by a direct interaction with the membrane itself. Some variants of P systems where the central role in their dynamics is played by the membranes have been considered. In these models, the membranes not only directly mediate the evolution and the communication of objects, but they can replicate themselves by means of a division process. Inspired by these features, P systems with active membranes [6] were introduced, based on processing multisets by means of non-cooperative rewriting rules, that is, rules where its left-hand side has at most only one object. Specifically, objects evolve inside membranes which can communicate between each other, can dissolve, and moreover (inspired by cellular mitosis process) can replicate by means of division rules. It is assumed that each membrane has associated an electrical polarization in any instant, one of the three possible: positive, negative, or neutral. P systems with active membranes are computationally complete, that is, any recursively enumerable set of vectors of natural numbers (in particular, each recursively enumerable set of natural numbers) can be generated by such a system [6]. Hence, they are equivalent in power to deterministic Turing machines. What about the computational efficiency of P systems with active membranes? The key is certainly in the use of division rules, as we can deduce from the socalled Milano theorem [13]: A deterministic P system with active membranes but without membrane division can be simulated by a deterministic Turing machine with a polynomial slowdown. However, P systems with active membranes which make use of division rules have the ability to provide efficient solutions to computationally hard problems, by making use of an exponential workspace created in a polynomial time. Specifically, NP-complete problems can be solved in polynomial time by families of P systems with active membranes, without dissolution rules and which use division rules only for elementary membranes [6]. Moreover, the class of decision problems which can be solved by families of P systems with active membranes with dissolution rules and which use division for elementary and non-elementary membranes is equal to PSPACE [8]. Consequently, the usual framework of P systems with active membranes and electrical polarizations for solving decision problems seems to be too powerful from the computational complexity point of view. With respect to the computational efficiency, in the classical framework of P system with active membranes, dissolution rules play an “innocent” role as well as P Systems with Active Membranes: Minimal Cooperation Only Outwards 255 division for non-elementary membranes. However, if electrical charges are removed then these kind of rules come to play a relevant role. Specifically, P systems with active membranes and without electrical charges were initially studied in [1, 2] by replacing electrical charges by the ability to change the label of the membranes. In this paper, polarizationless P systems with active membranes where labels of membranes keep unchanged by the application of rules, are considered. In this new framework, if dissolution rules are forbidden then only problems in class P can be solved in an efficient way, even in the case that division for non-elementary membranes are permitted [5]. Is the class of polarizationless P systems with active membranes, with dissolution but using only division rules for elementary membranes computationally efficient? If P6=NP, which is at all expected, then it is an open question, so-called P˘aun’s conjecture. In the seminal paper where P systems with active membranes were introduced, Gh. P˘aun says that “working with non-cooperative rules is natural from a mathematical point of view but from a biochemical point of view this is not only non-necessary, but also non-realistic: most of the chemical reactions involve two or more than two chemical compounds (and also produce two or more than two compounds)”. In this context, a restricted cooperation has been considered in the classical framework of polarizationless P systems with active membranes. Specifically, minimal cooperation (the left-hand side and the right-hand side of any rules have, at most, two objects) in object evolution rules, has been previously studied from a computational complexity point of view. A polynomial-time solution to the SAT problem by means of families of polarizationless P systems with active membranes, with minimal cooperation in object evolution rules, has been provided [9]. Recently, this result has been improved by considering minimal cooperation in object evolution rules with and additional restriction: the right-hand side of any rules has only one object (called minimal cooperation and minimal production) [11]. A relevant fact in these results is the following: dissolution rules and division rules for non-elementary membranes are not necessary to reach the computational efficiency. In this paper the role of minimal cooperation and minimal production in communication rules instead of object evolution rules, is studied from a complexity point of view. Specifically, by using families of membrane systems which use these syntactical ingredients, a polynomial-time solution to the SAT problem is provided but allowing division rules for non-elementary membranes. The paper is structured as follows. First, some basic notions are recalled and the terminology and notation to be used in the paper is presented. Then, Section 3 introduces the model that will be investigated in this paper: polarizationless P systems with active membranes, with minimal cooperation and minimal production in their communication rules. Section 4 contains the main result of this paper, showing that these systems are capable of solving an NP-complete problem in an efficient way. Finally, the paper concludes with some final remarks and ideas for future work. 262 L. Valencia-Cabrera et al. •First Checking stage: checking whether or not each clause of the input formula ϕis satisfied by the truth assignments generated in the previous stage, encoded by each membrane labelled by 2. This stage takes exactly np steps, being nthe number of the variables and pthe number of clauses of ϕ. •Second Checking stage: checking whether or not all clauses of the input formula ϕare satisfied by some truth assignment encoded by a membrane labelled by 2. This stage takes exactly np + 2psteps, being nthe number of variables and pthe number of clauses of ϕ. •Output stage: the system sends to the environment the right answer according to the results of the previous stage. This stage takes 2 steps if the answer is yes and 3 steps if the answer is no. 5.1 Generation stage Through this stage, all the different truth assignments for the variables associated with the Boolean formula ϕwill be generated within membranes labelled by 2, by the applications of rules from 5.2 and 5.3. In the first 2nsteps, 2nmembranes labelled by 1 and 2nmembranes labelled by 2, alternating between the division of membranes labelled by 2 (in odd steps) and the division of membranes labelled by 1 (in even steps). Proposition 1. Let C= (C0,C1,...,Cq)be a computation of the system Π(s(ϕ)) with input multiset cod(ϕ). (a0)For each 2k(0≤k≤n−1) at configuration C2kwe have the following: -C2k(0) = {α2k, β2k} - There are 2kempty membranes labelled by 1. - There are 2kmembranes labelled by 2 such that each of them contains ?the input multiset cod2k(ϕ); ?an object γ2k; and ? p copies of every Tiand Fi,1≤i≤n. ?objects ai,2k+1,k+ 1 ≤i≤n; and ?a different subset {r1,j, . . . , rk,j},k+ 1 ≤j≤2k, being r∈ {t, f}. (a1)For each 2k+ 1 (0≤j≤n−1) at configuration C2k+1 we have the following: -C2k+1(0) = {α2k+1, β2k+1} - There are 2kempty membranes labelled by 1. - There are 2k+1 membranes labelled by 2 such that each of them contains ?the input multiset cod2k+1(ϕ); ?an object γ2k+1; and ? p copies of every Tiand Fi,1≤i≤n. ?objects ai,2(k+1),k+ 1 ≤i≤n; and ?a different subset {r1,j, . . . , rk+1,j},k+1 ≤j≤2k+1, being r∈ {t, f}. (b)C2n(0) = {α2n, β2n}, and in C2nthere are 2nempty membranes labelled by 1; and 2nmembranes labelled by 2, such that each of them contains the input multiset cod2n(ϕ),pcopies of every Tiand Fi(1≤i≤n), an object γ2nand a different subset of objects ri,2n+1−i,1≤i≤n. P Systems with Active Membranes: Minimal Cooperation Only Outwards 263 Proof. (a) is going to be demonstrated by induction on k - The base case k= 0 is trivial because: (a0) at the initial configuration C0we have: C0(0) = {α0, β0}and there exists a single empty membrane labelled by 1 containing ; and a single membrane labelled by 2 containing the input multiset cod(ϕ), an object γ0,pcopies of Tiand Fi, being 1 ≤i≤n, the objects a1,1, . . . , an,1. Then, configuration C0yields configuration C1by applying the rules: [a1,1]2→[t1,1]2[f1,1]2 [ai,1→ai,2]2,for k+ 1 ≤i≤n [α0→α1]0 [β0→β1]0 [γ0→γ1]2 [xi,j,0→xi,j,1]2 [xi,j,0→xi,j,1]2 [x∗ i,j,0→x∗ i,j,1]2   for 1 ≤i≤n, 1≤j≤p (a1) at C1we have C1(0) = {α1, β1}and there exists a single empty membrane labelled by 1; and two membranes labelled by 2 containing the input multiset cod1(ϕ), an object γ1,pcopies of Tiand Fi, being 1 ≤i≤n, the objects a2,2, . . . , an,2and one with the object t1,1and the other one with the object f1,1. Then, the configuration C1yields configuration C2by applying the rules: [t1,1→t1,2]2 [f1,1→f1,2]2 [ [ ]2[ ]2]1→[ [ ]2]1[ [ ]2]1 [ai,2→ai,3]2,for 2 ≤i≤n [α1→α2]0 [β1→β2]0 [γ1→γ2]2 [xi,j,1→xi,j,2]2 [xi,j,1→xi,j,2]2 [x∗ i,j,1→x∗ i,j,2]2   for 1 ≤i≤n, 1≤j≤p Thus, C2(0) = {α2, β2}, and there exist two empty membranes labelled by 1; and two membranes labelled by 2 containing the input multiset cod2(ϕ), an object γ2,pcopies of Tiand Fi, being 1 ≤i≤n, the objects a2,3, . . . , an,3 and one with the object t1,2and the other one with the object f1,2. Hence, the result holds for k= 1. - Supposing, by induction, result is true for k(0 ≤k≤n−1) -C2k(0) = {α2k, β2k} - In C2kthere are 2kempty membranes labelled by 1. - In C2kthere are 2kmembranes labelled by 2 such that each of them contains ?the input multiset cod2k(ϕ); ?an object γ2k; ? p copies of Tiand Fi, 1 ≤i≤n. ?objects ai,2k+1,k+ 1 ≤i≤n; and 264 L. Valencia-Cabrera et al. ?a different subset {r1,j , . . . , rk,j },k+ 1 ≤j≤2k, being r∈ {t, f}. Then, configuration C2kyields configuration C2k+1 by applying the rules: [ak,2k+1 ]2→[tk,k ]2[fk,k ]2 [ai,2k+1 →ai,2k+2 ]2,for k+ 1 ≤i≤n [ti,j →ti,j+1 ]2 [fi,j →fi,j+1 ]2for 1 ≤i≤k−1, k + 1 ≤j≤2k [α2k→α2k+1 ]0 [β2k→β2k+1 ]0 [γ2k→γ2k+1 ]2 [xi,j,2k→xi,j,2k+1 ]2 [xi,j,1→xi,j,2k+1 ]2 [x∗ i,j,1→x∗ i,j,2k+1 ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -C2k+1(0) = {α2k+1, β2k+1} - In C2k+1 there are 2kempty membranes labelled by 1. - In C2k+1 there are 2k+1 membranes labelled by 2 such that each of them contains ?the input multiset cod2k+1(ϕ); ?an object γ2k+1; ? p copies of Tiand Fi, 1 ≤i≤n. ?objects ai,2(k+1),k+ 1 ≤i≤n; and ?a different subset {r1,j , . . . , rk+1,j },k+ 1 ≤j≤2k+ 1, being r∈ {t, f}. Then, configuration C2k+1 yields configuration C2(k+1) by applying the rules: [ti,j →ti,j+1 ]2 [fi,j →fi,j+1 ]2for 1 ≤i≤k+ 1, k + 1 ≤j≤2k+ 1 [ [ ]2[ ]2]1→[ [ ]2]1[ [ ]2]1 [ai,2(k+1) →ai,2(k+1)+1 ]2,for k+ 1 ≤i≤n [α2k+1 →α2(k+1) ]0 [β2k+1 →β2(k+1) ]0 [γ2k+1 →γ2(k+1) ]2 [xi,j,2k+1 →xi,j,2k+2 ]2 [xi,j,2k+1 →xi,j,2k+2 ]2 [x∗ i,j,2k+1 →x∗ i,j,2k+2 ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -C2(k+1)(0) = {α2(k+1), β2(k+1)} - In C2(k+1) there are 2k+1 empty membranes labelled by 1. - In C2(k+1) there are 2k+1 membranes labelled by 2 such that each of them contains ?the input multiset cod2(k+1)(ϕ); ?an object γ2(k+1); ? p copies of Tiand Fi, 1 ≤i≤n. ?objects ai,2(k+1)+1,k+ 1 ≤i≤n; and ?a different subset {r1,j , . . . , rk+1,j },k+ 1 ≤j≤2(k+ 1) + 1. P Systems with Active Membranes: Minimal Cooperation Only Outwards 265 Hence, the result holds for k+ 1. - In order to prove (b) it is enough to notice that, on the one hand, from (a) configuration C2n−1holds: -C2n−1(0) = {α2n−1, β2n−1} - In C2n−1there are 2n−1empty membranes labelled by 1. - In C2n−1there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2n−1p(ϕ); ?an object γ2n−1; ? p copies of Tiand Fi, 1 ≤i≤n; and ?a different subset of objects ri,2n−i, 1 ≤i≤n. Then, configuration C2n−1yields C2nby applying the rules: [ti,2n−i→ti,2n+1−i]2 [fi,2n−i→fi,2n+1−1]2for 1 ≤i≤n [ [ ]2[ ]2]1→[ [ ]2]1[ [ ]2]1 [α2n−1→α2n]0 [β2n−1→β2n]0 [γ2n−1→γ2n]2 [xi,j,2n−1→xi,j,2n]2 [xi,j,2n−1→xi,j,2n]2 [x∗ i,j,2n−1→x∗ i,j,2n]2   for 1 ≤i≤n, 1≤j≤p Then, we have C2n(0) = {α2n, β2n}, and there exist 2nempty membranes labelled by 1; and 2nmembranes labelled by 2 containing the input multiset cod2n(ϕ), an object γ2n,pcopies of Tiand Fi, being 1 ≤i≤nand a different multiset of objects ri,2n+1−i, being 1 ≤i≤n.  When the tree structure is created, we start assigning a truth assignment to each branch. It is executed in the next 2np−nsteps. The last nsteps are different from the previous ones, so they deserve another proposition of the following one. Proposition 2. Let C= (C0,C1,...,Cq)be a computation of the system Π(s(ϕ)) with input multiset cod(ϕ). (a0)For each k(1≤k≤n) and l(0≤l≤p−1) at configuration C2n+2ln+kwe have the following: -C2n+2ln+k(0) = {α2n+2ln+k, β2n+2ln+k} - There are 2nmembranes labelled by 1 such that each of them contains a different subset of objects ri,2n+2ln+k−i+1,1≤i≤k, being r∈ {t, f}. - There are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2n+2ln+k(ϕ); ?an object γ2n+2ln+k; ? p copies of every Tiand Fi,1≤i≤nif the truth assignment associated to the branch contains its corresponding tior fiobject; otherwise, there are p−lcopies if k+ 1 ≤i≤n,p−l−1otherwise; and 266 L. Valencia-Cabrera et al. ?objects ri,2n+2ln+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. (a1)For each k(1≤k≤n) and l(0≤l≤p−1) at configuration C3n+2ln+kwe have the following: -C2n+2ln+k(0) = {α2n+2ln+k, β2n+2ln+k} - There are 2nmembranes labelled by 1 such that each of them contains a different subset of objects ri,3n+ln+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. - There are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod3n+2ln+k(ϕ); ?an object γ3n+2ln+k; ? p copies of every Tiand Fi,1≤i≤nif the truth assignment associated to the branch contains its corresponding tior fiobject, and p−lcopies otherwise; and ?objects ri,3n+2ln+k−i+1,1≤i≤k, being r∈ {t, f}. (b)C2np(0) = {α2np, β2np}, and in C2np there are 2nempty membranes labelled by 1; and 2nmembranes labelled by 2 such that each of them contains the input multiset cod2np(ϕ), an object γ2np,pcopies of every Tiand Fi,1≤i≤n if the truth assignment associated to the branch contains its corresponding ti or fiobject, and 1 object otherwise and objects ri,2np−i+1,1≤i≤n, being r∈ {t, f}, that is, the truth assignment associated with the branch. Proof. (a) is going to be demonstrated by induction on l - The base case l= 0 is going to be demonstrated by induction on k (a0) The base case k= 1 is trivial because: - at configuration C2nwe have: C2n(0) = {α2n, β2n}and there exist 2n empty membranes labelled by 1 containing ; and 2nmembranes labelled by 2 containing the input multiset cod2n(ϕ), an object γ2n,pcopies of Tiand Fi, being 1 ≤i≤nand a different subset of objects ri,2n−i+1, 1≤i≤n, being r∈ {t, f}, the corresponding truth assignment of the branch. Then, configuration C2nyields configuration C2n+1 by applying the rules: [ti,2nFi]2→ti,2n+1[ ]2 [fi,2nTi]2→fi,2n+1[ ]2 [ti,2n+1−i→ti,2n+2−i]2 [fi,2n+1−i→fi,2n+2−1]2for 2 ≤i≤n [α2n→α2n+1 ]0 [β2n→β2n+1 ]0 [γ2n→γ2n+1 ]2 [xi,j,2n→xi,j,2n+1 ]2 [xi,j,2n→xi,j,2n+1 ]2 [x∗ i,j,2n→x∗ i,j,2n+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, C2n+1(0) = {α2n+1, β2n+1}, and there exist 2nmembranes labelled by 1 containing an object r1,2n+1, being r∈ {t, f}; and 2nmem- branes labelled by 2 containing the input multiset cod2n+1(ϕ), an object γ2n+1,pcopies of Tiand Fi, being 2 ≤i≤n, and p−1 copies of T1 P Systems with Active Membranes: Minimal Cooperation Only Outwards 267 (respectively, Fi) if object f1,2n(resp., t1,2n) was within membrane labelled by 2 at configuration C2n, and pcopies of F1(resp., T1), and a different subset of objects ri,2n−i+2, 2 ≤i≤n, being r∈ {t, f}. - Supposing, by induction, result is true for k(1 ≤k≤n) -C2n+k(0) = {α2n+k, β2n+k} - In C2n+kthere are 2nmembranes labelled by 1 such that each of them contains objects ri,2n+k−i+1, 1 ≤i≤k, being r∈ {t, f}. - In C2n+kthere are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2n+k(ϕ); ?an object γ2n+k; ? p copies of every Tiand Fi, 1 ≤i≤nif the truth assignment associated to the branch contains its corresponding tior fiobject, p−1 objects Tiand Fi(1 ≤i≤k) otherwise; and ?a different subset of objects ri,2n+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. Then, configuration C2n+kyields configuration C2n+k+1 by applying the rules: [tk+1,2nFk+1 ]2→tk+1,2n+1[ ]2 [fk+1,2nTk+1 ]2→fk+1,2n+1[ ]2 [ti,2n+k−i+1 →ti,2n+k−i+2 ]2 [fi,2n+k−i+1 →fi,2n+k−i+2 ]2for k+ 2 ≤i≤n [ti,2n+k−i+1 →ti,2n+k−i+2 ]1 [fi,2n+k−i+1 →fi,2n+k−i+2 ]1for 1 ≤i≤k [α2n+k→α2n+k+1 ]0 [β2n+k→β2n+k+1 ]0 [γ2n+k→γ2n+k+1 ]2 [xi,j,2n+k→xi,j,2n+k+1 ]2 [xi,j,2n+k→xi,j,2n+k+1 ]2 [x∗ i,j,2n+k→x∗ i,j,2n+k+1 ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -C2n+k+1(0) = {α2n+k+1, β2n+k+1} - In C2n+k+1 there are 2nmembranes labelled by 1 such that each of them contains objects ri,2n+k−i+2, 1 ≤i≤k+ 1, being r∈ {t, f}. - In C2n+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2n+k+1(ϕ); ?an object γ2n+k+1; ? p copies of every Tiand Fi, 1 ≤i≤nif the truth assignment associated to the branch contains its corresponding tior fiobject, p−1 objects Tiand Fi(1 ≤i≤k+ 1) otherwise; and ?a different subset of objects ri,2n+k−i+2,k+ 2 ≤i≤n, being r∈ {t, f}. (a1) The base case k= 1 is trivial because: 268 L. Valencia-Cabrera et al. - at configuration C3nwe have C3n(0) = {α3n, β3n}and there exist 2n membranes labelled by 1 containing and a different subset of objects ri,3n+1−i, 1 ≤i≤n, being r∈ {t, f}, that is, the corresponding truth assignment of the branch; and 2nmembranes labelled by 2 containing the input multiset cod3n(ϕ), an object γ3n,pcopies of Tiand Fi, being 1≤i≤nif the truth assignment associated to the branch contains its corresponding object tior fi,p−1 objects otherwise. Then, configuration C3nyields configuration C3n+1 by applying the rules: t1,3n[ ]2→[t1,3n+1 ]2 f1,3n[ ]2→[f1,3n+1 ]2 [ti,3n−i+1 →ti,3n−i+2 ]1 [fi,3n−i+1 →fi,3n−i+2 ]1for 2 ≤i≤n [α3n→α3n+1 ]0 [β3n→β3n+1 ]0 [γ3n→γ3n+1 ]2 [xi,j,3n→xi,j,3n+1 ]2 [xi,j,3n→xi,j,3n+1 ]2 [x∗ i,j,3n→x∗ i,j,3n+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, C3n+1(0) = {α3n+1, β3n+1}, and there exist 2nmembranes labelled by 1 containing a different subset of objects ri,3n−i+2, 2 ≤i≤n, being r∈ {t, f}; and 2nmembranes labelled by 2 containing the input multiset cod3n+1(ϕ), an object γ3n+1,pcopies of Tiand Fi, being 1≤i≤nif the truth assignment associated to the branch contains its corresponding object tior fi,p−1 objects otherwise and an object r1,3n+1, being r∈ {t, f}. - Supposing, by induction, result is true for k(1 ≤k≤n) -C3n+k(0) = {α3n+k, β3n+k} - In C3n+kthere are 2nmembranes labelled by 1 such that each of them contains objects ri,3n+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. - In C3n+kthere are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod3n+k(ϕ); ?an object γ3n+k; ? p copies of every Tiand Fifor 1 ≤i≤nor their corresponding ti or fiis assigned to that branch, p−lcopies otherwise; and ?a different subset of objects ri,3n+k−i+1, 1 ≤i≤k, being r∈ {t, f}. Then, configuration C3n+kyields configuration C3n+k+1 by applying the rules: tk+1,3n[ ]2→[tk+1,3n+1 ]2 fk+1,3n[ ]2→[fk+1,3n+1 ]2 [ti,3n+k−i+1 →ti,3n+k−i+2 ]1 [fi,3n+k−i+1 →fi,3n+k−i+2 ]1for k+ 2 ≤i≤n [ti,3n+k−i+1 →ti,3n+k−i+2 ]2 [fi,3n+k−i+1 →fi,3n+k−i+2 ]2for 1 ≤i≤k P Systems with Active Membranes: Minimal Cooperation Only Outwards 269 [α3n+k→α3n+k+1 ]0 [β3n+k→β3n+k+1 ]0 [γ3n+k→γ3n+k+1 ]2 [xi,j,3n+k→xi,j,3n+k+1 ]2 [xi,j,3n+k→xi,j,3n+k+1 ]2 [x∗ i,j,3n+k→x∗ i,j,3n+k+1 ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -C3n+k+1(0) = {α3n+k+1, β3n+k+1} - In C3n+k+1 there are 2nmembranes labelled by 1 such that each of them contains objects ri,3n+k−i+2,k+ 2 ≤i≤n, being r∈ {t, f}. - In C3n+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod3n+k+1(ϕ); ?an object γ3n+k+1; ? p copies of every Tiand Fifor 1 ≤i≤nor the corresponding tior fiis assigned to that branch, p−lcopies otherwise; and ?a different subset of objects ri,3n+k−i+2, 1 ≤i≤k+ 1, being r∈ {t, f}. - Supposing, by induction, result is true for l(0 ≤l≤p−1) (a0) The base case k= 1 is trivial because: - at configuration C2n+(l+1)n1we have: C2n+(l+1)n(0) = {α2n+(l+1)n, β2n+(l+1)n}and there exist 2nempty membranes labelled by 1; and 2n membranes labelled by 2 containing the input multiset cod2n+(l+1)n(ϕ), an object γ2n+(l+1)n,pcopies of Tiand Fi, being 1 ≤i≤n, and p−l copies for Ti(resp. Fi) objects that are in a branch with an object fi (resp. ti) and a different subset of objects ri,2n+(l+1)n−i+1, 1 ≤i≤n, being r∈ {t, f}, the corresponding truth assignment of the branch. Then, configuration C2n+(l+1)nyields configuration C2n+(l+1)n+1 by applying the rules: [ti,2n+(l+1)nFi]2→ti,2n+(l+1)n+1[ ]2 [fi,2n+(l+1)nTi]2→fi,2n+(l+1)n+1[ ]2 [ti,2n+(l+1)n+1−i→ti,2n+(l+1)n+2−i]2 [fi,2n+(l+1)n+1−i→fi,2n+(l+1)n+2−i]2for 2 ≤i≤n [α2n+(l+1)n→α2n+(l+1)n+1 ]0 [β2n+(l+1)n→β2n+(l+1)n+1 ]0 [γ2n+(l+1)n→γ2n+(l+1)n+1 ]2 [xi,j,2n+(l+1)n→xi,j,2n+(l+1)n+1 ]2 [xi,j,2n+(l+1)n→xi,j,2n+(l+1)n+1 ]2 [x∗ i,j,2n+(l+1)n→x∗ i,j,2n+(l+1)n+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, C2n+(l+1)n+1(0) = {α2n+(l+1)n+1, β2n+(l+1)n+1}, and there exist 2nmembranes labelled by 1 containing and an object r1,2n+(l+1)n+1, 1Note that (l+ 1)n=ln +n, and it has been demonstrated in the first step of the induction that it is correct. 270 L. Valencia-Cabrera et al. being r∈ {t, f}; and 2nmembranes labelled by 2 containing the input multiset cod2n+(l+1)n+1(ϕ), an object γ2n+(l+1)n+1,pcopies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti(resp. fi) object exists in that branch, otherwise p−lcopies of Fi(resp. Ti) if 2 ≤i≤n,p−l−1 otherwise and a different subset of objects ri,2n+(l+1)n−i+2, 2 ≤i≤n, being r∈ {t, f}. - Supposing, by induction, result is true for k(1 ≤k≤n) -C2n+(l+1)n+k(0) = {α2n+(l+1)n+k, β2n+(l+1)n+k} - In C2n+(l+1)n+kthere are 2nmembranes labelled by 1 such that each of them contains objects ri,2n+(l+1)n+k−i+1, 1 ≤i≤k, being r∈ {t, f}. - In C2n+(l+1)n+kthere are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2n+(l+1)n+k(ϕ); ?an object γ2n+(l+1)n+k; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti (resp. fi) object exists in that branch, otherwise p−lcopies of Fi (resp. Ti) if k+ 1 ≤i≤n,p−l−1 otherwise; and ?a different subset of objects ri,2n+(l+1)n+k−i+1,k+1 ≤i≤n, being r∈ {t, f}. Then, configuration C2n+kyields configuration C2n+(l+1)n+k+1 by applying the rules: [tk+1,2n+(l+1)nFk+1 ]2→tk+1,2n+(l+1)n+1[ ]2 [fk+1,2n+(l+1)nTk+1 ]2→fk+1,2n+(l+1)n+1[ ]2 [ti,2n+(l+1)n+k−i+1 →ti,2n+k−i+2 ]2 [fi,2n+(l+1)n+k−i+1 →fi,2n+k−i+2 ]2for k+ 2 ≤i≤n [ti,2n+(l+1)n+k−i+1 →ti,2n+(l+1)n+k−i+2 ]1 [fi,2n+(l+1)n+k−i+1 →fi,2n+(l+1)n+k−i+2 ]1for 1 ≤i≤k [α2n+(l+1)n+k→α2n+(l+1)n+k+1 ]0 [β2n+(l+1)n+k→β2n+(l+1)n+k+1 ]0 [γ2n+(l+1)n+k→γ2n+(l+1)n+k+1 ]2 [xi,j,2n+(l+1)n+k→xi,j,2n+(l+1)n+k+1 ]2 [xi,j,2n+(l+1)n+k→xi,j,2n+(l+1)n+k+1 ]2 [x∗ i,j,2n+(l+1)n+k→x∗ i,j,2n+(l+1)n+k+1 ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -C2n+(l+1)n+k+1(0) = {α2n+(l+1)n+k+1, β2n+(l+1)n+k+1} - In C2n+(l+1)n+k+1 there are 2nmembranes labelled by 1 such that each of them contains objects ri,2n+(l+1)n+k−i+2, 1 ≤i≤k+1, being r∈ {t, f}. - In C2n+(l+1)n+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2n+(l+1)n+k+1(ϕ); ?an object γ2n+(l+1)n+k+1; P Systems with Active Membranes: Minimal Cooperation Only Outwards 271 ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti (resp. fi) object exists in that branch, otherwise p−lcopies of Fi (resp. Ti) if k+ 2 ≤i≤n,p−l−1 otherwise; and ?a different subset of objects ri,2n+(l+1)n+k−i+2,k+2 ≤i≤n, being r∈ {t, f}. (a1) The base case k= 1 is trivial because: - at configuration C3n+(l+1)nwe have C3n+(l+1)n(0) = {α3n+(l+1)n, β3n+(l+1)n}and there exist 2nmembranes labelled by 1 containing a different subset of objects ri,3n+(l+1)n−i+1, 1 ≤i≤n, being r∈ {t, f}, that is, the corresponding truth assignment of the branch; and 2nmem- branes labelled by 2 containing the input multiset cod3n+(l+1)n(ϕ), an object γ3n+(l+1)nand pcopies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti(resp. fi) object exists in that branch, and p−l copies of Fi(resp. Ti). Then, configuration C3n+(l+1)nyields configuration C3n+(l+1)n+1 by applying the rules: t1,3n+(l+1)n[ ]2→[t1,3n+(l+1)n+1 ]2 f1,3n+(l+1)n[ ]2→[f1,3n+(l+1)n+1 ]2 [ti,3n+(l+1)n−i+1 →ti,3n+(l+1)n−i+2 ]1 [fi,3n+(l+1)n−i+1 →fi,3n+(l+1)n−i+2 ]1for 2 ≤i≤n [α3n+(l+1)n→α3n+(l+1)n+1 ]0 [β3n+(l+1)n→β3n+(l+1)n+1 ]0 [γ3n+(l+1)n→γ3n+(l+1)n+1 ]2 [xi,j,3n+(l+1)n→xi,j,3n+(l+1)n+1 ]2 [xi,j,3n+(l+1)n→xi,j,3n+(l+1)n+1 ]2 [x∗ i,j,3n+(l+1)n→x∗ i,j,3n+(l+1)n+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, C3n+(l+1)n+1(0) = {α3n+(l+1)n+1, β3n+(l+1)n+1}, and there exist 2nmembranes labelled by 1 containing a different subset of objects ri,3n+(l+1)n−i+2, 2 ≤i≤n, being r∈ {t, f}; and 2nmembranes labelled by 2 containing the input multiset cod3n+(l+1)n+1(ϕ), an object γ3n+(l+1)n+1,pcopies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti(resp. fi) object exists in that branch, and p−lcopies of Fi(resp. Ti) and an object r1,3n+(l+1)n+1, being r∈ {t, f}. - Supposing, by induction, result is true for k(1 ≤k≤n) -C3n+(l+1)n+k(0) = {α3n+(l+1)n+k, β3n+(l+1)n+k} - In C3n+(l+1)n+kthere are 2nmembranes labelled by 1 such that each of them contains objects ri,3n+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. - In C3n+(l+1)n+kthere are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod3n+(l+1)n+k(ϕ); ?an object γ3n+(l+1)n+k; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti (resp. fi) object exists in that branch, and p−lcopies of Fi(resp. Ti) 278 L. Valencia-Cabrera et al. [αn+2np+k→αn+2np+k+1 ]0 [βn+2np+k→βn+2np+k+1 ]0 [γn+2np+k→γn+2np+k+1 ]2 [xi,j,n+2np+k→xi,j,n+2np+k+1 ]2 [xi,j,n+2np+k→xi,j,n+2np+k+1 ]2 [x∗ i,j,n+2np+k→x∗ i,j,n+2np+k+1 ]2   for 1 ≤i≤n, 1≤j≤p [c1,t →c1,t+1 ]1for 0 ≤t≤k−1 Therefore, the following holds -Cn+2np+k+1 ={αn+2np+k+1, βn+2np+k+1} - In Cn+2np+k+1 there are 2nmembranes labelled by 1 such that each of them contains ? m objects c1,t (0 ≤t≤k), that is, the number of variables with the corresponding truth assignment that makes true the clause C1; and ? n +k+ 1 −mobjects #. - In Cn+2np+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the (n−k+ 1)-th last elements of codn+2np+k+1(ϕ)1 1; ?the input multiset codn+2np+k+1(ϕ)p 2, ?an object γn+2np+k+1; and ? p copies of objects Tior Fi,k+2 ≤i≤n,p−1 copies if 1 ≤i≤k+1, corresponding to the truth assignment assigned to the branch. - Supposing, by induction, result is true for l(0 ≤l≤p−1) - The base case k= 1 is trivial because: - at configuration Cn+2np+(l+1)nwe have: Cn+2np+(l+1)n(0) = {αn+2np+(l+1)n, βn+2np+(l+1)n}and there exist 2nmembranes labelled by 1 containing mobjects cj,t (1 ≤j≤l, 0 ≤t≤ln −1), that is, the number of variables with the corresponding truth assignment that makes true the clauses from C1to Cland n+ (l+ 1)n−mobjects #; and 2nmembranes labelled by 2 containing the input multiset codn+2np+(l+1)n(ϕ)p l+1, an object γn+2np+(l+1)nand p−lcopies of objects Tior Fi, 1 ≤i≤n. Then, configuration Cn+2np+(l+1)nyields configuration Cn+2np+(l+1)n+1 by applying the rules: [T1x1,1,n+2np+(l+1)n]2−→ cl+1,0[ ]2 [T1x1,1,n+2np+(l+1)n]2−→ #[ ]2 [T1x∗ 1,1,n+2np+(l+1)n]2−→ #[ ]2 [F1x1,1,n+2np+(l+1)n]2−→ cl+1,0[ ]2 [F1x1,1,n+2np+(l+1)n]2−→ #[ ]2 [F1x∗ 1,1,n+2np+(l+1)n]2−→ #[ ]2 [αn+2np+(l+1)n→αn+2np+(l+1)n+1 ]0 [βn+2np+(l+1)n→βn+2np+(l+1)n+1 ]0 [γn+2np+(l+1)n→γn+2np+(l+1)n+1 ]2 P Systems with Active Membranes: Minimal Cooperation Only Outwards 279 [xi,j,n+2np+(l+1)n→xi,j,n+2np+(l+1)n+1 ]2 [xi,j,n+2np+(l+1)n→xi,j,n+2np+(l+1)n+1 ]2 [x∗ i,j,n+2np+(l+1)n→x∗ i,j,n+2np+(l+1)n+1 ]2   for 1≤i≤n 1≤j≤p [cj,t →c1,t+1 ]1for 1 ≤j≤l+ 1,0≤t≤ln −1 Thus, Cn+2np+(l+1)n+1(0) = {αn+2np+(l+1)n+1, βn+2np+(l+1)n+1}, and there exist 2nmembranes labelled by 1 containing mobjects cj,t (1 ≤j≤l+ 1, 0≤t≤ln), that is, the number of variables with the corresponding truth assignment that makes true the clauses from C1to Cl+1 and n+ (l+ 1)n+ 1 −mobjects #; and 2nmembranes labelled by 2 containing the last n−1 elements of codn+2np+(l+1)n+1(ϕ)l+1 l+1, the input multiset codn+2np+(l+1)n+1(ϕ)p l+2,p−lcopies of Tior Fi, being 2 ≤i≤n, and p−l−1 copies of T1or F1. - Supposing, by induction, result is true for k(1 ≤k≤n) -Cn+2np+(l+1)n+k(0) = {αn+2np+(l+1)n+k, βn+2np+(l+1)n+k} - In Cn+2np+(l+1)n+kthere are 2nmembranes labelled by 1 such that each of them contains ? m objects cj,t (1 ≤j≤l+ 1, 0 ≤t≤ln +k−1), that is, the number of variables with the corresponding truth assignment that makes true clauses from C1to Cl+1; and ? n + (l+ 1)n+k+ 1 −mobjects #. - In Cn+2np+(l+1)n+kthere are 2nmembranes labelled by 2 such that each of them contains ?the (n−k)-th last elements of codn+2np+(l+1)n+k(ϕ)l+1 l+1; ?the input multiset codn+2np+(l+1)n+k(ϕ)p l+2, ?an object γn+2np+(l+1)n+k; and ? p −lcopies of objects Tior Fi,k+ 1 ≤i≤n,p−l−1 copies if 1≤i≤k, corresponding to the truth assignment assigned to the branch. Then, configuration Cn+2np+(l+1)n+kyields configuration Cn+2np+(l+1)n+k+1 by applying the rules: [Tkx1,1,n+2np+(l+1)n+k]2−→ cl+1[ ]2 [Tkx1,1,n+2np+(l+1)n+k]2−→ #[ ]2 [Tkx∗ 1,1,n+2np+(l+1)n+k]2−→ #[ ]2 [Fkx1,1,n+2np+(l+1)n+k]2−→ #[ ]2 [Fkx1,1,n+2np+(l+1)n+k]2−→ cl+1[ ]2 [Fkx∗ 1,1,n+2np+(l+1)n+k]2−→ #[ ]2 [αn+2np+(l+1)n+k→αn+2np+(l+1)n+k+1 ]0 [βn+2np+(l+1)n+k→βn+2np+(l+1)n+k+1 ]0 [γn+2np+(l+1)n+k→γn+2np+(l+1)n+k+1 ]2 [xi,j,n+2np+(l+1)n+k→xi,j,n+2np+(l+1)n+k+1 ]2 [xi,j,n+2np+(l+1)n+k→xi,j,n+2np+(l+1)n+k+1 ]2 [x∗ i,j,n+2np+(l+1)n+k→x∗ i,j,n+2np+(l+1)n+k+1 ]2   for 1≤i≤n 1≤j≤p [cj,t →cj,t+1 ]1for 1 ≤j≤l+ 1,0≤t≤ln +k−1 280 L. Valencia-Cabrera et al. Therefore, the following holds -Cn+2np+(l+1)n+k+1(0) = {αn+2np+(l+1)n+k+1, βn+2np+(l+1)n+k+1} - In Cn+2np+(l+1)n+k+1 there are 2nmembranes labelled by 1 such that each of them contains ? m objects cj,t (1 ≤j≤l+ 1, 0 ≤t≤ln +k), that is, the number of variables with the corresponding truth assignment that makes true clauses from C1to Cl+1; and ? n + (l+ 1)n+k+ 1 −mobjects #. - In Cn+2np+(l+1)n+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the (n−(k+ 1))-th last elements of codn+2np+(l+1)n+k+1(ϕ)l+1 l+1, ?the input multiset codn+2np+(l+1)n+k+1(ϕ)p l+1, ?an object γn+2np+(l+1)n+k+1; ? p −lcopies of objects Tior Fi,k+ 2 ≤i≤n,p−l−1 copies if 1≤i≤k+ 1, corresponding to the truth assignment assigned to the branch. - In order to prove (b) it is enough to notice that, on the one hand, from (a) configuration Cn+3np−16holds: -Cn+3np−1(0) = {αn+3np−1, βn+3np−1} - In Cn+3np−1there are 2nmembranes labelled by 1 such that each of them contains ? m objects cj,t (1 ≤j≤p, 0 ≤t≤np−2), that is, the number of variables with the corresponding truth assignment that makes true clauses from C1to Cp; and ? n +np −1−mobjects #. - In Cn+3np−1there are 2nmembranes labelled by 2 such that each of them contains ?the last element of codn+3np−1(ϕ)p p; ?an object γn+3np−1; and ?an object Tnor Fncorresponding to the truth assignment assigned to the branch. Then, configuration Cn+3np−1yields Cn+3np by applying the rules: [Tnxn,p,n+3np−1]2−→ cp,0[ ]2 [Tnxn,p,n+3np−1]2−→ #[ ]2 [Tnx∗ n,p,n+3np−1]2−→ #[ ]2 [Fnxn,p,n+3np−1]2−→ #[ ]2 [Fnxn,p,n+3np−1]2−→ cp,0[ ]2 [Fnx∗ n,p,n+3np−1]2−→ #[ ]2 [αn+2np+(l+1)n+k→αn+2np+(l+1)n+k+1 ]0 [βn+2np+(l+1)n+k→βn+2np+(l+1)n+k+1 ]0 [γn+2np+(l+1)n+k→γn+2np+(l+1)n+k+1 ]2 6Note that n+ 3np −1 = n+ 3n(p−1) + (n−1) P Systems with Active Membranes: Minimal Cooperation Only Outwards 281 [xi,j,n+2np+(l+1)n+k→xi,j,n+2np+(l+1)n+k+1 ]2 [xi,j,n+2np+(l+1)n+k→xi,j,n+2np+(l+1)n+k+1 ]2 [x∗ i,j,n+2np+(l+1)n+k→x∗ i,j,n+2np+(l+1)n+k+1 ]2   for 1≤i≤n 1≤j≤p [cj,t →cj,t+1 ]2for 1 ≤j≤l+ 1,0≤t≤ln +k−1 Therefore, the following holds -Cn+3np(0) = {αn+3np, βn+3np} - In Cn+3np there are 2nmembranes labelled by 1 such that each of them contains ? m objects cj,t (1 ≤j≤p, 0 ≤t≤np −1), that is, the number of variables with the corresponding truth assignment that makes true clauses from C1to Cp; and ? n +np −mobjects #. - In Cn+3np there are 2nmembranes labelled by 2 such that each of them contains an object γn+3np.  5.3 Second checking stage At this stage, started at configuration Cn+3np, we try to determine the truth assignments that make true the input formula ϕ, using rules from 5.6. We are going to divide this stage in two phases. The first one will be devoted to send in all the objects cj, for 1 ≤j≤pin order to get them ready for the next phase. Let k=ln +i(0 ≤l≤p−1,1≤i≤n), so we can refer to each clause (l−1) when we are doing the verification. Let m= p P j=1 mj, being mjthe number of objects cj,k in each membrane 1 at step Cn+3np. In this stage, we cannot be sure of how many objects cl+1,k are present at each membrane when i6= 0 7, so if we cannot be sure of that, we are going to say that there are emj(remember that emjis always less than or equal to mj) objects within membrane 1. We will ignore objects # since they have no effect from here. Proposition 5. Let C= (C0,C1,...,Cq)be a computation of the system Π(s(ϕ)) with input multiset cod(ϕ). (a)For each k(1≤k≤np −1) at configuration Cn+3np+kwe have the following: -Cn+3np+k(0) = {αn+3np+k, βn+3np+k} - There are 2nmembranes labelled by 1 such that each of them contains eml+1 objects cl+1,t ((p−1)n+ 1 ≤t≤np −1) and mjobjects cj,t (l+ 2 ≤j≤ p, ln +i≤t≤np −1) - There are 2nmembranes labelled by 2 such that each of them contains ?an object γn+3np+k; and ? mjobjects cjfor 1≤j≤land ml+1 −eml+1 objects cl+1 7That is because objects cj,k do not have to be created consecutively. 282 L. Valencia-Cabrera et al. (b)Cn+4np(0) = {αn+4np, βn+4np}, there are 2nempty membranes labelled by 1; and 2nmembranes labelled by 2, such that each of them contains mobjects cj (1≤j≤p) and an object γn+4np. Proof. (a) is going to be demonstrated by induction on k - The base case k= 1 is trivial because: At configuration Cn+3np we have: Cn+3np(0) = {αn+3np, βn+3np}and there exist 2nmembranes labelled by 1 containing mobjects cj,t (1 ≤j≤k, 0≤t≤np −1); and 2nmembranes labelled by 2 containing an object γn+3np. Then, configuration Cn+3np yields configuration Cn+3np+1 by applying the rules: [αn+3np →αn+3np+1 ]0 [βn+3np →βn+3np+1 ]0 [γn+3np →γn+3np+1 ]2 [cj,t −→ cj,t+1]1,for 1 ≤j≤p, 0≤k≤np −2 c1,np−1[ ]2−→ [c1]2 Thus, Cn+3np+1(0) = {αn+3np+1, βn+3np+1}, and there exist 2nmembranes labelled by 2 containing em1objects c1and mjobjects cj(2 ≤j≤p); and 2n membranes labelled by 1 containing an object γn+3np+1 and m1−em1objects c18. Hence, the result holds for k= 1. - Supposing, by induction, result is true for k(1 ≤k≤np −1) -Cn+3np+k(0) = {αn+3np+k, βn+3np+k} - In Cn+3np+kthere are 2nmembranes labelled by 1 such that each of them contains eml+1 objects cl+1,t ((p−1)n+ 1 ≤t≤np −1) and mjobjects cj,t (l+ 2 ≤j≤p, ln +i≤t≤np −1). - In Cn+3np+kthere are 2nmembranes labelled by 2 such that each of them contains ?an object γn+3np+k; and ? mjobjects cjfor 1 ≤j≤land ml+1 −eml+1 objects cl+1. Then, configuration Cn+3np+kyields configuration Cn+3np+kby applying the rules: [αn+3np+k→αn+3np+k+1 ]0 [βn+3np+k→βn+3np+k+1 ]0 [γn+3np+k→γn+3np+k+1 ]2 [cj,t −→ cj,t+1]1,for l+ 1 ≤j≤p, 0≤k≤np −2 cl+1,np−1[ ]2−→ [cl+1]2 Therefore, the following holds -Cn+3np+k+1(0) = {αn+3np+k+1, βn+3np+k+1} - In Cn+3np+k+1 there are 2nmembranes labelled by 1 such that each of them contains eml+1 objects cl+1,t+1 ((p−1)n+ 1 ≤t≤np −1) and mjobjects cj,t+1 (l+ 2 ≤j≤p, ln +i≤t≤np −1). 8That is, if the truth assignment of variable 1 made true clause 1, then an object c1,0 were created at (2n+ 2np + 1)-th step, and it is going to be sent to the corresponding membrane 2. So, m1−em1can be 0 or 1 in this step. P Systems with Active Membranes: Minimal Cooperation Only Outwards 283 - In Cn+3np+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?an object γn+3np+k+1; and ? mjobjects cjfor 1 ≤j≤land ml+1 −eml+1 objects cl+1. Hence, the result holds for k+ 1. - In order to prove (b) it is enough to notice that, on the one hand, from (a) configuration Cn+4np−1holds: -Cn+4np−1(0) = {αn+4np−1, βn+4np−1} - In Cn+4np−1there are 2nmembranes labelled by 1 such that each of them contains - In Cn+4np−1there are 2nmembranes labelled by 2 such that each of them contains empobjects cp,np. ?an object γn+4np−1; and ? mjobjects cjfor 1 ≤j≤p−1 and mp−emp9objects cp. Then, configuration Cn+4np−1yields configuration Cn+4np by applying the rules: [αn+4np−1→αn+4np ]0 [βn+4np−1→βn+4np ]0 [γn+4np−1→γn+4np ]2 cp,np[ ]2−→ [cp]2 Then, we have Cn+4np(0) = {αn+4np, βn+4np}, and there exist 2nempty membranes labelled by 1; and there exist 2nmembranes labelled by 2 containing an object γn+4np and mobjects cj(1 ≤j≤p).  When objects cjare within the membranes labelled by 2, we can start to check if all the clauses of the input formula ϕare satisfied by any truth assignment. As we use objects cjto denote that clause Cjhas been satisfied by some variable, it can be possible that some cjare missing, that is, that for some j, 1 ≤j≤p,cj does not appear in any membrane labelled by 2 in C2n+4np. Let e jbe the index j10 of that clause. It is going to take 2psteps. Proposition 6. Let C= (C0,C1,...,Cq)be a computation of the system Π(s(ϕ)) with input multiset cod(ϕ). (a0)For each 2k+ 1 (0≤k≤p−1) at configuration Cn+4np+2k+1 we have the following: -Cn+4np+2k+1(0) = {αn+4np+2k+1, βn+4np+2k+1} - There are 2nmembranes labelled by 1 such that each of them contains an object dk+1 if and only if the truth assignment associated to the branch makes true the first k+ 1 clauses. - There are 2nmembranes labelled by 2 such that each of them contains 9In this case, empcan only take two values: 0 or 1. 10 If e jis not defined, we are going to suposse that it is equal to p+ 1. 284 L. Valencia-Cabrera et al. ?an object γn+4np or de j−1(respectively, an object dk) if the corresponding truth assignment does not make true (resp., makes true) the clause C1 or Cj(2≤j≤p) (resp., the first kclauses); and ? mj−1objects cjfor 1≤j≤min(e j, k + 1) and mjobjects cjfor min(e j, k + 2) ≤j≤p. (a1)For each 2k(1≤k≤p−2) at configuration Cn+4np+2kwe have the following: -Cn+4np+2k(0) = {αn+4np+2k, βn+4np+2k} - There are 2nempty membranes labelled by 1. - There are 2nempty membranes labelled by 2 such that each of them contains ?an object γn+4np or de j−1if the corresponding truth assignment does not make true the clause C1or Cj(2≤j≤p); and ? mj−1objects cjfor 1≤j≤min(e j, k)and mjobjects cjfor min(e j, k+ 1) ≤j≤p. (b)Cn+4np+2p−1(0) = {αn+4np+2p−1, βn+4np+2p−1}, and in Cn+4np+2p−1there are 2nmembranes labelled by 1, such that each of them contains an object dpif and only if the corresponding truth assignment makes true the input formula ϕ(de j−1otherwise); and 2nmembranes labelled by 2, such that each of them contains mj−1objects cjfor 1≤j≤min(e j, p+1),mjobjects cjfor min(e j, p+ 1) ≤j≤pand an object γn+4np (respectively, de j) if clause C1(resp., Cj) is not satisfied by the corresponding truth assignment. Proof. (a) is going to be demonstrated by induction on k - The base case k= 1 is trivial because: (a0) at configuration Cn+4np we have: Cn+4np(0) = {αn+4np, βn+4np}and there exist 2nempty membranes labelled by 1; and there exist 2nmembranes labelled by 2 containing an object γn+4np and mobjects cj(1 ≤j≤p). Then, configuration Cn+4np yields configuration Cn+4np+1 by applying the rules: [αn+4np →αn+4np+1 ]0 [βn+4np →βn+4np+1 ]0 [γ4np+2nc1]2−→ d1[ ]2 (a1) at Cn+4np+1(0) = {αn+4np+1, βn+4np+1}and there exist 2nmembranes labelled by 1 containing an object d1if and only if there was at least one object c1within membrane labelled by 1 at configuration Cn+4np; and 2n membranes labelled by 2 containing an object γn+4np if and only if there were no objects c1at configuration Cn+4np,m1−1 (respectively, m1) objects c1if there was any object cjin this membrane in the previous configuration (resp., m1) and mjobjects cjfor 2 ≤j≤p. Then, the configuration Cn+4np+1 yields configuration Cn+4np+2 by applying the rules: [αn+4np+1 →αn+4np+2 ]0 [βn+4np+1 →βn+4np+2 ]0 d1[ ]2−→ [d1]2 Thus, Cn+4np+2(0) = {αn+4np+2, βn+4np+2}, and there exist 2nempty membranes labelled by 1; and there exist 2nmembranes labelled by 2 P Systems with Active Membranes: Minimal Cooperation Only Outwards 285 containing an object d1(respectively, γn+4np) if the corresponding truth assignment makes true (resp., doesn’t make true) clause C1,m1−1 (resp., m1) objects c1and mjobjects cjfor 1 ≤j≤p. Hence, the result holds for k= 1. - Supposing, by induction, result is true for k(0 ≤k≤p−1) -Cn+4np+2k(0) = {αn+4np+2k, βn+4np+2k} - In Cn+4np+2kthere are 2nempty membranes labelled by 1. - In Cn+4np+2kthere are 2nmembranes labelled by 2 such that each of them contains ?an object γn+4np or de j−1(respectively, an object dk) if the corresponding truth assignment does not make true (resp., makes true) the clause C1 or Cj(2 ≤j≤p) (resp., the first kclauses); and ? mj−1 objects cjfor 1 ≤j≤min(e j, k + 1) and mjobjects cjfor min(e j, k + 2) ≤j≤p. Then, configuration Cn+4np+2kyields configuration Cn+4np+2k+1 by applying the rules: [αn+4np+2k→αn+4np+2k+1 ]0 [βn+4np+2k→βn+4np+2k+1 ]0 [dkck+1 ]2−→ dk+1[ ]2 Therefore, the following holds -Cn+4np+2k+1(0) = {αn+4np+2k+1, βn+4np+2k+1} - In Cn+4np+2k+1 there are 2nmembranes labelled by 1 such that each of them contains an object dk+1 if and only if the corresponding truth assignment makes true the first k+ 1 clauses. - In Cn+4np+2k+1 there are 2nmembranes labelled by 2 such that each of them contains ?an object γn+4np or de j−1if the corresponding truth assignment does not make true the clause C1or Cj(2 ≤j≤p); and ? mj−1 objects cjfor 1 ≤j≤min(e j, k) and mjobjects cjfor min(e j, k + 1) ≤j≤p. Then, configuration Cn+4np+2k+1 yields Cn+4np+2k+2 by applying the rules: [αn+4np+2k+1 →αn+4np+2k+2 ]0 [βn+4np+2k+1 →βn+4np+2k+2 ]0 dk+1[ ]2−→ [dk+1 ]2 Therefore, the following holds -Cn+4np+2k+2(0) = {αn+4np+2k+2, βn+4np+2k+2} - In Cn+4np+2k+2 there are 2nempty membranes labelled by 1. - In Cn+4np+2k+2 there are 2nmembranes labelled by 2 such that each of them contains ?an object γn+4np or de j−1(respectively, an object dk+1) if the corresponding truth assignment does not make true (resp., makes true) the clause C1or Cj(2 ≤j≤p) (resp., the first k+ 1 clauses); and 286 L. Valencia-Cabrera et al. ? mj−1 objects cjfor 1 ≤j≤min(e j, k + 2) and mjobjects cjfor min(e j, k + 3) ≤j≤p. Hence, the result holds for k+ 1. - In order to prove (b) it is enough to notice that, on the one han, from (a) configuration Cn+4np+2p−2holds: -Cn+4np+2p−2(0) = {αn+4np+2p−2, βn+4np+2p−2} - In Cn+4np+2p−2there are 2nempty membranes labelled by 1. - In Cn+4np+2p−2there are 2nmembranes labelled by 2 such that each of them contains - an object γn+4np or de j−1(respectively, dp−1) if the corresponding truth assignment does not make true the clause C1or Cj(2 ≤j≤p−1) (resp., makes true clauses Cj(1 ≤j≤p−1)); and -mj−1 objects cjfor 1 ≤j≤min(e j, p −1) and mjobjects cjfor min(e j, p)≤j≤p Then, configuration Cn+4np+2p−2yields configuration Cn+4np+2p−1by applying the rules: [αn+4np+2p−2→αn+4np+2p−1]0 [βn+4np+2p−2→βn+4np+2p−1]0 [dp−1cp]2−→ dp[ ]2 Then, we have Cn+4np+2p−1(0) = {αn+4np+2p−1, βn+4np+2p−1}, and in Cn+4np+2p−1there are 2nmembranes labelled by 1, such that each of them contains an object dpif and only if the corresponding truth assignment makes true the input formula ϕ(de j−1otherwise); and 2nmem- branes labelled by 2, such that each of them contains mj−1 objects cjfor 1≤j≤min(e j, p + 1), mjobjects cjfor min(e j, p + 1) ≤j≤pand an object γn+4np (respectively, de j) if clause C1(resp., Cj) is not satisfied by the corresponding truth assignment.  5.4 Output stage The output phase starts at configuration Cn+4np+2p−1, and takes exactly two steps when there is an affirmative answer and three steps when there is a negative one. Rules from 5.7 are devoted to compute this stage. -Affirmative answer: In this case, at configuration Cn+4np+2p−1, in some membrane 1 there is an object dp. By applying the rule [ dp]1−→ dp[ ]1(at the same time that [ αn+4np+2p−1→αn+4np+2p]0and [ βn+4np+2p−1→ βn+4np+2p]0are executed), an object dpis produced in membrane 0. Then by applying the rules [ α4np+n+2pdp]0−→ yes[ ]0and [ βn+4np+2p→ βn+4np+2p+1 ]0, an object yes is released to environment and the computation halts. P Systems with Active Membranes: Minimal Cooperation Only Outwards 287 -Negative answer: In this case, at configuration Cn+4np+2p−1, there are no membranes labelled by 1 that contains an object dp, so the only rules executed are [ αn+4np+2p−1→αn+4np+2p]0and [ βn+4np+2p−1→βn+4np+2p]0. Rule [βn+4np+2p→βn+4np+2p+1 ]0is executed in the next step. Thus, at configuration Cn+4np+2p+1 in membrane labelled by 0 we execute have a copy of object αn+4np+2pand a copy of object βn+4np+2p+1. By applying the rule [α4np+n+2pβ4np+n+2p+1]0−→ no[ ]0an object no is released to the environment and then the computation halts. 5.5 Result Theorem 1. SAT ∈PMCDAM0(+es,mcmpout,−d,+n). Proof. The family Πof P systems previously constructed verifies the following: (a) The family Πis polynomially uniform by Turing machines because for each n, p ∈N, the rules of Π(hn, pi) of the family are recursively defined from n, p ∈N, and the amount of resources needed to build an element of the family is of a polynomial order in nand p, as shown below: – Size of the alphabet: 15n2p2 2+3n2p+3n2+np2+35np 2+5n+6p+6 ∈Θ(n2p2). – Initial number of membranes: 3 ∈Θ(1). – Initial number of objects in membranes: 3np +n+ 3 ∈Θ(np). – Number of rules: 15n2p2 2+ 7n2p+np2+33np 2+ 4n+ 6p+ 4 ∈Θ(n2p2). – Maximal number of objects involved in any rule: 3 ∈Θ(1). (b) The family Πis polynomially bounded with regard to (SAT,cod, s): indeed for each instance ϕof the SAT problem, any computation of the system Π(s(ϕ)) with input multiset cod(ϕ) takes at most 2n+ 4np + 2p+ 5 computation steps. (e) The family Πis sound with regard to (SAT,cod, s): indeed for each instance ϕof the SAT problem, if the computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation, then ϕis satisfiable. (f) The family Πis complete with regard to (SAT,cod, s): indeed, for each instance ϕof the SAT problem such that ϕis satisfiable, any computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation. Therefore, the family Πof P systems previously constructed solves the SAT problem in polynomial time and in a uniform way. Corollary 1. NP ∪co −NP ⊆PMCDAM0(+es,mcmpout,−d,+n). Proof. It suffices to notice that SAT problem is a NP-complete problem, SAT ∈PMCDAM0(+es,mcmpout,−d,+n), and the complexity class PMCDAM0(+es,mcmpout,−d,+n)is closed under polynomial-time reduction and under complement.