Seventh Brainstorming Week on Membrane Computing. Sevilla, February 2-February 6, 2009 Volume I : RGNC REPORT 1/2009

RGNC REPORT 1/2009 Seventh Brainstorming Week on Membrane Computing Sevilla, February 2–February 6, 2009 Volume I Rosa Guti´errez-Escudero, Miguel Angel Guti´errez-Naranjo, Gheorghe P˘aun, Ignacio P´erez-Hurtado, Agust´ın Riscos-N´u˜nez Editors Research Group on Natural Computing REPORTS UNIVERSIDAD DE SEVILLA Seventh Brainstorming Week on Membrane Computing Sevilla, February 2–February 6, 2009 Volume I Rosa Guti´errez-Escudero, Miguel Angel Guti´errez-Naranjo, Gheorghe P˘aun, Ignacio P´erez-Hurtado, Agust´ın Riscos-N´u˜nez Editors Seventh Brainstorming Week on Membrane Computing Sevilla, February 2–February 6, 2009 Volume I Rosa Guti´errez-Escudero, Miguel Angel Guti´errez-Naranjo, Gheorghe P˘aun, Ignacio P´erez-Hurtado, Agust´ın Riscos-N´u˜nez Editors RGNC REPORT 1/2009 Research Group on Natural Computing Sevilla University F´enix Editora, Sevilla, 2009 c Autores I.S.B.N.(Obra completa): 978-84-613-2836-9 I.S.B.N.(Volumen I): 978-84-613-2837-6 I.S.B.N.(Volumen II): 978-84-613-2839-0 Dep´osito Legal: SE-????–09 Edita: F´enix Editora C/ Patricio S´aenz 13, 1–B 41004 Sevilla [email protected] Telf. 954 41 29 91 Printed by Publidisa Preface These proceedings, consisting of two volumes, contain the papers emerged from the Seventh Brainstorming Week on Membrane Computing (BWMC), held in Sevilla, from February 2 to February 6, 2009, in the organization of the Research Group on Natural Computing 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 the next five editions took place in Sevilla at the beginning of February 2004, 2005, 2006, 2007, and 2008, respectively. In the style of previous meetings in this series, the seventh BWMC was conceived as a period of active interaction among the participants, with the emphasis on exchanging ideas and cooperation; this time, however, there were much more presentations than in the previous years, but still these presentations were “provocative”, mainly proposing new ideas, open problems, research topics, results which need further improvements. The efficiency of this type of meetings was again proved to be very high and the present volumes prove this assertion. As already usual, the number of participants was around 40, most of them computer scientists, but also a few biologists were present. It is important to note that several new names appeared in the membrane computing community, also bringing new view points and research topics to this research area. The papers included in these volumes, arranged in the alphabetic order of the authors, were collected in the form available at a short time after the brainstorming; several of them are still under elaboration. The idea is that the proceedings are a working instrument, part of the interaction started during the stay of authors in Sevilla, meant to make possible a further cooperation, this time having a written support. A selection of the papers from these volumes will be considered for publication in a special issues of International Journal of Computers, Control and Communication. After the first BWMC, a special issue of Natural Computing – volume 2, number 3, 2003, and a special issue of New Generation Computing – volume 22, number 4, 2004, were published; papers from the second BWMC have appeared in vi Preface a special issue of Journal of Universal Computer Science – volume 10, number 5, 2004, as well as in a special issue of Soft Computing – volume 9, number 5, 2005; a selection of papers written during the third BWMC have appeared in a special issue of International Journal of Foundations of Computer Science – volume 17, number 1, 2006); after the fourth BWMC a special issue of Theoretical Computer Science was edited – volume 372, numbers 2-3, 2007; after the fifth edition, a special issue of International Journal of Unconventional Computing was edited – volume 5, number 5, 2009; finally, a selection of papers elaborated during the sixth BWMC has appeared in a special issue of Fundamenta Informaticae – volume 87, number 1, 2008. Other papers elaborated during the seventh BWMC will be submitted to other journals or to suitable 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. Alhazov Artiom, Hiroshima University, Japan, [email protected] 2. Ardelean Ioan, Institute of Biology of the Romanian Academy, Bucharest, Romania, [email protected] 3. Bogdan Aman, A.I.Cuza University, Iasi, Romania, [email protected] 4. Caravagna Giulio, University of Pisa, Italy, [email protected] 5. Ceterchi Rodica, University of Bucharest, Romania, [email protected] 6. Colomer-Cugat M. Angels, University of Lleida, Spain, [email protected] 7. Cord´on-Franco Andr´es, University of Sevilla, Spain, [email protected] 8. Csuhaj-Varj´u Erzs´ebet, Hungarian Academy of Sciences, Budapest, Hungary, [email protected] 9. D´ıaz-Pernil Daniel, University of Sevilla, Spain, [email protected] 10. Frisco Pierluigi, Heriot-Watt University, United Kingdom, [email protected] 11. Garc´ıa-Quismondo Manuel, University of Sevilla, Spain, [email protected] 12. Graciani-D´ıaz Carmen, University of Sevilla, Spain, [email protected] 13. Guti´errez-Naranjo Miguel ´ Angel, University of Sevilla, Spain, [email protected] Preface vii 14. Guti´errez-Escudero Rosa, University of Sevilla, Spain, [email protected] 15. Henley Beverley, University of Sevilla, Spain, [email protected] 16. Ipate Florentin, University of Pitesti, Romania, [email protected] 17. Ishdorj Tseren-Onolt, Abo Akademi, Finland, [email protected] 18. Krassovitskiy Alexander, Rovira i Virgili University, Tarragona, Spain, [email protected] 19. Leporati Alberto, University of Milano-Bicocca, Italy, [email protected] 20. Mart´ınez-del-Amor Miguel Angel, University of Sevilla, Spain, [email protected] 21. Mauri Giancarlo, University of Milano-Bicocca, Italy, [email protected] 22. Mingo Postiglioni Jack Mario, Carlos Tercero University, Madrid, Spain, [email protected] 23. Murphy Niall, NUI Maynooth, Ireland, [email protected] 24. Obtu lowicz Adam, Polish Academy of Sciences, Poland, [email protected] 25. Orejuela-Pinedo Enrique Francisco, University of Sevilla, Spain, [email protected] 26. Pagliarini Roberto, University of Verona, Italy, [email protected] 27. Pan Linqiang, Huazhong University of Science and Technology, Wuhan, Hubei, China, [email protected] 28. P˘aun Gheorghe, Institute of Mathematics of the Romanian Academy, Bucharest, Romania, and University of Sevilla, Spain, [email protected], [email protected] 29. P´erez-Hurtado-de-Mendoza Ignacio, University of Sevilla, Spain, [email protected] 30. P´erez-Jim´enez Mario de Jes´us, University of Sevilla, Spain, [email protected] 31. Porreca Antonio, University of Milano-Bicocca, Italy, [email protected] 32. Riscos-N´u˜nez Agust´ın, University of Sevilla, Spain, [email protected] 33. Rogozhin Yurii, Institute of Mathematics and Computer Science, Chisinau, Moldova, [email protected] 2 A. Alhazov et al. Membrane systems are a convenient framework of describing computations on trees. Since membrane systems are an abstraction of living cells, the membranes are arranged hierarchically, yielding a tree structure. 2 Definitions Membrane computing is a recent domain of natural computing started by Gh. P˘aun in [2]. The components of a membrane system are a cell-like membrane structure, in the regions of which one places multisets of objects which evolve in a synchronous maximally parallel manner according to given evolution rules associated with the membranes. The necessary definitions are given in the following subsection; see also [3] for an overview of the domain and [5] for the comprehensive bibliography. 2.1 Computing by P systems Let Obe a finite set of elements called symbols; the set of words over Ois denoted by O∗, and the empty word is denoted by λ. Definition 1. A P system with string-objects and input is a tuple Π=¡O, Σ, H, E, µ, M1,· · · , Mp, R, i0¢, where: •Ois the working alphabet of the system whose elements are called objects. •Σis an input alphabet. •His an alphabet whose elements are called labels. •Eis the set of polarizations. •µis a membrane structure (a rooted tree) consisting of pmembranes injectively labeled by elements of H. •Miis an initial multiset of strings over Oassociated with membrane i,1≤i≤ p. •Ris a finite set of rules defining the behavior of objects from Oand membranes labeled by elements of H. •i0identifies the input region. A configuration of a P system is its “snapshot”, i.e., the current membrane structure and the multisets of strings of objects present in regions of the system. While initial configuration is C0= (µ, M1,···, Mp), each subsequent configuration C0is obtained from the previous configuration Cby maximally parallel application of rules to objects and membranes, denoted by C⇒C0(no further rules are applicable together with the rules that transform Cinto C0). A computation is thus a sequence of configurations starting from C0, respecting relation ⇒and ending in a halting configuration (i.e., such one that no rules are applicable). If Mis a multiset of strings over the input alphabet Σ⊆O, then the initial configuration of a P system Πwith an input Mover alphabet Σand input region i0is (µ, M1,· · · , Mi0−1, Mi0∪M, Mi0+1,· · · , Mp). Dictionary Search by P Systems with String-Objects 3 2.2 P systems with active membranes To speak about P systems with active membranes, we need to specify the rules, i.e., the elements of the set Rin the description of a P system. Due to the nature of the problem of this paper, the standard model was generalized in the following: •Cooperative rules: a rule can consider consecutive symbols in a string (otherwise, the time complexity would be much higher). •String replication (to return the result without removing it from the dictionary). •Membrane creation (to add words to the dictionary). Hence, the rules can be of the following forms: (a∗) [ a→b]e h, for h∈H, e ∈E, a, b ∈O∗ (evolution rules, associated with membranes and depending on the label and the polarization of the membranes, but not directly involving the membranes, in the sense that the membranes are neither taking part in the application of these rules nor are they modified by them); (a∗ r) [ a→b||c]e h, for h∈H, e ∈E, a, b, c ∈O∗ (like the previous case, but with string replication); (b∗)a[ ]e1 h→[b]e2 h, for h∈H, e1, e2∈E, a, b ∈O∗ (communication rules; an object is introduced into the membrane; the object can be modified during this process, as well as the polarization of the membrane can be modified, but not its label); (c∗) [ a]e1 h→[ ]e2 hb, for h∈H, e1, e2∈E, a, b ∈O∗ (communication rules; an object is sent out of the membrane; the object can be modified during this process; also the polarization of the membrane can be modified, but not its label); (d∗) [ a]e h→b, for h∈H, e ∈E, a, b ∈O (dissolving rules; in reaction with an object, a membrane can be dissolved, while the object specified in the rule can be modified); (g∗) [ a→[b]e2 g]e1 h, for g, h ∈H, e1, e2∈E, a, b ∈O∗ (membrane creation rules; an object is moved into a newly created membrane and possibly modified). Additionally, we will write ∅in place of some strings on the right-hand side of the rules, meaning that the entire string is deleted. The rules of types (a∗),(a∗ r) and (g∗) are considered to only involve objects, while all other rules are assumed to involve objects and membranes mentioned in 4 A. Alhazov et al. their left-hand side. An application of a rule consists in replacing a substring described in the left-hand side of a string in the corresponding region (i.e., associated to a membrane with label hand polarization efor rules of types (a∗),(a∗ r) and (d∗), or associated to a membrane with label hand polarization e1for rules of type (c∗), or immediately outer of such a membrane for rules of type (b∗) ), by a string described in the right-hand side of the rule, moving the string to the corresponding region (that can be the same as the source region immediately inner or immediately outer, depending on the rule type), and updating the membrane structure accordingly if needed (changing membrane polarization, creating or dissolving a membrane). The rules can only be applied simultaneously if they involve different objects and membranes (we repeat that rules of type (a) are not considered to involve a membrane), and such parallelism is maximal if no further rules are applicable to objects and membranes that were not involved. 3 Dictionary Dictionary search represents computing a string-valued function {ui−→ vi|1≤i≤d} defined on a finite set of strings. We represent such a dictionary by the skin membrane containing the membrane structure corresponding to the prefix tree of {ui|1≤i≤d}, with strings $vi$0in regions corresponding to the nodes associated to ui. Due to technical reasons, we assume that for every l∈A1, the skin contains a membrane with label l. We also suppose that the source words are non-empty. For instance, the dictionary {bat −→ flying,bit −→ stored}is represented by [ [ ]0 a[[[$flying$0]0 t]0 a[[$stored$0]0 t]0 i]b[ ]0 c· · · [ ]0 z]0 0 Let A1, A2be the alphabets of the source and target languages, respectively. Consider a P system corresponding to the given dictionary. Π=¡O, Σ, H, E, µ, M1,· · · , Mp, R, i0¢, O=A1∪A2∪ {?,?0,$,$0,$1,$2,fail} ∪ {?i|1≤i≤11}∪{!i|1≤i≤4}, Σ=A1∪A2∪ {?,?0,!,$,$0}, H=A1∪ {0}, E ={0,+,−}, µand sets Mi,1≤i≤p, are defined as described above, i0= 1, so only the rules and input semantics still have to be defined. Dictionary Search by P Systems with String-Objects 5 3.1 Dictionary search To translate a word u, input the string ?u?0in region 1. Consider the following rules. S1 ?l[ ]0 l→[?]0 l,l∈A1 Propagation of the input into the membrane structure, reaching the location corresponding to the input word. S2 [ ??0]0 l→[ ]− l∅,l∈A1 Marking the region corresponding to the source word. S3 [ $ →$1||$2]− l,l∈A1 Replicating the translation. S4 [ $2]e l→[ ]0 l$2,l∈H,e∈ {−,0} Sending one copy of the translation to the environment. S5 [ $1→$ ]0 l,l∈A1 Keeping the other copy in the dictionary. The system will send the translation of uin the environment. This is a simple example illustrating search. If the source word is not in the dictionary, the system will be blocked without giving an answer. The following subsection shows a solution to this problem. 3.2 Search with fail The set of rules below is considerably more involved than the previous one. However, it handles 3 cases: a) the target word is found, b) the target word is missing in the target location, c) the target location is unreachable. F1 [ ? →?1||?2]0 0 Replicate the input. F2 [ ?2→?3]0 0 Delay the second copy of the input for one step. F3 ?1l[ ]0 l→[ ?1]+ l,l∈A1 Propagation of the first copy towards the target location, changing the polarization of the entered membrane to +. F4 ?3l[ ]+ l→[ ?3]0 l,l∈A1 Propagation of the second copy towards the target location, restoring the polarization of the entered membrane. 6 A. Alhazov et al. F5 [ ?1l→[ ?4]− l]0 k,l, k ∈A1 If a membrane corresponding to some symbol of the source word is missing, then the first copy of the input remains in the same membrane, while the second copy of the input restores its polarization. Creating a membrane to handle the failure. F6 [ ?1?0→?7]0 l,l∈A1 Target location found, marking the first input copy. F7 [ ?7]0 l→[ ]− l∅,l∈A1 Marking the target location. In either case, some membrane has polarization −. It remains to send the answer out, or fail if it is absent. The membrane should be deleted in the fail case. F8 [ $ →$1||$2]− l,l∈A1 Replicating the translation. F9 [ $2]e l→[ ]0 l$2,l∈H,e∈ {0,−} Sending one copy of the translation out. F10 [ $1→$ ]0 l,l∈A1 Keeping the other copy in the dictionary. F11 [ ?3→?5]− l,l∈A1 The second copy of input will check if the translation is available in the current region. F12 ?3l[ ]− l→[ ?5]− l,l∈A1 The second copy of input enters the auxiliary membrane with polarization −. By now the second copy of the input is in the region corresponding to either the search word, or to its maximal prefix plus one letter (auxiliary one). F13 [ ?5→?6]− l,l∈A1 It waits for one step. F14 [ ?6→ ∅ ]0 l,l∈A1 If the target word has been found, the second copy of the input is erased. F15 [ ?6]− l→[ ]0 l?8,l∈A1 If not, the search fails. F16 [ ?8]0 l→[ ]0 l?8,l∈A1 Sending the fail notification to the skin. F17 [ ?8l→?8]0 0 Dictionary Search by P Systems with String-Objects 7 Erasing the remaining part of the source word. F18 [ ?8?0]0 l→[ ]0 lfail Answering fail. F19 [ ?4→?9]− l,l∈A1 F20 [ ?9→?10 ]− l,l∈A1 F21 [ ?10 →?11 ]− l,l∈A1 If the target location was not found, the first input copy waits for 3 steps while the membrane with polarization −handles the second input copy. F22 [ ?11 ]0 l→ ∅,l∈A1 Erasing the auxiliary membrane. 3.3 Dictionary update To add a pair of words u−→ vto the dictionary, input the string !u$v$0in region 1. Consider the following rules. U1 [ ! →!1||!2]0 0 Replicate the input. U2 [ !2→!3]0 0 Delay the second copy of the input for one step. U3 !1l[ ]0 l→[ !1]+ l,l∈A1 Propagation of the first copy towards the target location, changing the polarization of the entered membrane to +. U4 !3l[ ]+ l→[ !3]0 l,l∈A1 Propagation of the second copy towards the target location, restoring the polarization of the entered membrane. U5 [ !1→!4]0 l,l∈A1 If a membrane corresponding to some symbol of the source word is missing, then the first copy of the input remains in the same membrane, while the second copy of the input restores its polarization. Marking the fist copy of the input for creation of missing membranes. U6 [ !4l→[ !4]+ l]0 k,l, k ∈A1 Creating missing membranes. U7 [ !4$→$ ]0 l,l∈A1 8 A. Alhazov et al. Releasing the target word in the corresponding location. U8 [ !3$→ ∅ ]0 l,l∈A1 Erasing the second copy of the input. We underline that the constructions presented above also hold in a more general case, i.e., when the dictionary is a multi-valued function. Indeed, multiple translations can be added to the dictionary as multiple strings in the region associated to the input word. The search for a word with multiple translations will lead to all translations sent to the environment. The price to pay is that the construction is no longer deterministic, since the order of application of rules S4 or F9 to different translations is arbitrary. Nevertheless, the constructions remain “deterministic modulo the order in which the translations are sent out”. 4 Discussion In this paper we presented the algorithms of searching in a dictionary and completing it implemented as membrane systems. We underline that the systems are constructed as reusable modules, so they are suitable for using as sub-algorithms for solving more complicated problems. The scope of handling dictionaries is not limited to the dictionaries in the classical sense. Understanding a dictionary as introduced in Section 3, i.e., a stringvalued function defined on a finite set of strings, leads to direct applicability of the proposed methods to handle alphabets, lexicons, thesaura, dictionaries of exceptions, and even databases. Acknowledgments All authors gratefully acknowledge the support by the Science and Technology Center in Ukraine, project 4032. Artiom Alhazov gratefully acknowledges the support of the Japan Society for the Promotion of Science and the Grant-in-Aid for Scientific Research, project 20·08364. Yurii Rogozhin gratefully acknowledges the support of the European Commission, project MolCIP, MIF1-CT-2006-021666. References 1. H. Kitano: Challenges of massive parallelism. Proceedings of the 13th International Joint Conference on Artificial Intelligence, Chambery, France, 1993, vol. 1, 813–834. 2. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 3. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, 2002. 4. E. Sumita, K. Oi, O. Furuse, H. Iida, T. Higuchi, N. Takahashi, H. Kitano: Examplebased machine translation on massively parallel processors. Proceedings of the 13th International Joint Conference on Artificial Intelligence, Chambery, France, 1993, vol. 2, 1283–1289. 5. P systems webpage. http://ppage.psystems.eu/. P Systems with Minimal Insertion and Deletion Artiom Alhazov1,3, Alexander Krassovitskiy2, Yurii Rogozhin2,3, Sergey Verlan4 1IEC, Department of Information Engineering, Graduate School of Engineering Hiroshima University, Higashi-Hiroshima 739-8527 Japan 2Research Group on Mathematical Linguistics, Rovira i Virgili University Av. Catalunya, 35, Tarragona 43002 Spain [email protected] 3Institute of Mathematics and Computer Science, Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova {artiom,rogozhin}@math.md 4LACL, D´epartement Informatique, Universit´e Paris 12 61 av. G´en´eral de Gaulle, 94010 Cr´eteil, France [email protected] Summary. In this paper we consider insertion-deletion P systems with priority of deletion over the insertion. We show that such systems with one symbol context-free insertion and deletion rules are able to generate P sRE. If one-symbol one-sided context is added to insertion or deletion rules but no priority is considered, then all recursively enumerable languages can be generated. The same result holds if a deletion of two symbols is permitted. We also show that the priority relation is very important and in its absence the corresponding class of P systems is strictly included in MAT . 1 Introduction The operations of insertion and deletion are fundamental in formal language theory, and generative mechanisms based on them were considered (with linguistic motivation) for some time, see [14] and [6]. Related formal language investigations can be found in several places; we mention only [8], [10], [16], [19]. In the last years, the study of these operations has received a new motivation from molecular computing, see [3], [9], [21], [23], [15]. In general form, an insertion operation means adding a substring to a given string in a specified (left and right) context, while a deletion operation means removing a substring of a given string from a specified (left and right) context. A finite set of insertion-deletion rules, together with a set of axioms provide a language generating device: starting from the set of initial strings and iterating insertion-deletion operations as defined by the given rules we get a language. The number of axioms, the length of the inserted or deleted strings, as well as the 10 A. Alhazov et al. length of the contexts where these operations take place are natural descriptional complexity measures in this framework. As expected, insertion and deletion operations with context dependence are very powerful, leading to characterizations of recursively enumerable languages. Most of the papers mentioned above contain such results, in many cases improving the complexity of insertion-deletion systems previously available in the literature. Some combinations of parameters lead to systems which are not computationally complete [17], [11] or even decidable [24]. However, if these systems are combined with the distributed computing framework of P systems [20], then their computational power may strictly increase, see [12], [13]. In this paper we study P systems with insertion and deletion rules of one symbol without context. We show that this family is strictly included in MAT , however some non-context-free languages may be generated. If Parikh vectors are considered, then the corresponding family equals to P sMAT . When a priority of deletion over insertion is introduced, P sRE can be characterized, but in terms of language generation such systems cannot generate a lot of languages because there is no control on the position of an inserted symbol. If one-sided contextual insertion or deletion rules are used, then this can be controlled and all recursively enumerable languages can be generated. The same result holds if a context-free deletion of two symbols is allowed. 2 Definitions All formal language notions and notations we use here are elementary and standard. The reader can consult any of the many monographs in this area – for instance, [22] – for the unexplained details. We denote by |w|the length of a word wand by |w|athe number of occurrences of symbol ain w. For a word w∈V∗we denote by ∆(w) all words w0having the same number of letters as w,∆(w) = {w0|,|w0|a=|w|afor all a∈V}and we denote by t⊥ the binary shuffle operation. By card(V) we denote the cardinality of the set V. An InsDel system is a construct ID = (V, T, A, I, D),where Vis an alphabet, T⊆V,Ais a finite language over V, and I, D are finite sets of triples of the form (u, α, v), α6=λ, where uand vare strings over Vand λdenotes the empty string. The elements of Tare terminal symbols (in contrast, those of V−Tare called nonterminals), those of Aare axioms, the triples in Iare insertion rules, and those from Dare deletion rules. An insertion rule (u, α, v)∈Iindicates that the string αcan be inserted in between uand v, while a deletion rule (u, α, v)∈Dindicates that αcan be removed from the context (u, v). As stated otherwise, (u, α, v)∈I corresponds to the rewriting rule uv →uαv, and (u, α, v)∈Dcorresponds to the rewriting rule uαv →uv. We refer by =⇒to the relation defined by an insertion or deletion rule. The language L(ID) generated by ID is defined as {w∈T∗|A3x=⇒∗w}. P Systems with Minimal Insertion and Deletion 11 The complexity of an InsDel system ID = (V, T, A, I, D) is described by the vector (n, m, m0;p, q, q0) called size, where n= max{|α| | (u, α, v)∈I}, p = max{|α| | (u, α, v)∈D}, m= max{|u| | (u, α, v)∈I}, q = max{|u| | (u, α, v)∈D}, m0= max{|v| | (u, α, v)∈I}, q0= max{|v| | (u, α, v)∈D}. We also denote by INSm,m0 nDELq,q0 pcorresponding families of languages. Traditionally, in the literature, instead of pairs m/m0and q/q0the maximum of both numbers is used. However, such a complexity measure is not accurate and it cannot distinguish between universality and non-universality cases, see [24] and [11]. If some of the parameters n, m, m0, p, q, q0is not specified, then we write symbol ∗ instead. For example, INS0,0 ∗DEL0,0 ∗denotes the family of languages generated by context-free InsDel systems. InsDel systems of a “sufficiently large” size characterize RE, the family of recursively enumerable languages. Now we present a definition of insertion-deletion P systems. The insertiondeletion tissue P systems are defined in an analogous manner. An insertion-deletion P system is a construct Π= (O, T, µ, M1,· · · , Mn, R1,· · · , Rn), where •Ois a finite alphabet, •T⊆Ois the terminal alphabet, •µis the membrane (tree) structure of the system which has nmembranes (nodes) and it can be represented by a word over the alphabet of correctly nested marked parentheses, •Mi,for each 1 ≤i≤n, is a finite language associated to the membrane i, •Ri,for each 1 ≤i≤n, is a set of insertion and deletion rules with target indicators associated to region i, of the following forms: (u, x, v;tar)a, where (u, x, v) is an insertion rule, and (u, x, v;tar)e, where (u, x, v) is a deletion rule, and the target indicator tar is from the set {here, inj, out |1≤j≤n}. An n-tuple (N1,· · · , Nn) of finite languages over Ois called a configuration of Π. The transition between the configurations consists in applying the insertion and deletion rules in parallel to all possible strings, non-deterministically, and following the target indications associated with the rules. A sequence of transitions between configurations of a given insertion-deletion P system Πstarting from the initial configuration is called a computation with respect to Π. We say that Πgenerates L(Π), the result of its computations. It consists of all strings over Tever sent out of the system during its computations. We denote by ELSPk(insm,m0 p, delq,q0 p) the family of languages L(Π) generated by insertion-deletion P systems with at most k≥1 membranes and insertion and deletion rules of size at most (n, m, m0;p, q, q0). We omit the letter Eif T= O. In this paper we also consider insertion-deletion P systems where deletion rules have a priority over insertion rules; the corresponding class is denoted as 18 A. Alhazov et al. µ= [ [ [ Y p∈Q+ µhp+iY p∈Q− µhp−i Y p∈Qs µhpsi]3]2]1,where µhp+i, µhp−i are defined as in Theorem 5 and, µhpsi= [ [ [ [ [ ]ps 7]ps 4[ ]ps 6]ps 3[ ]ps 5]ps 2]ps 1 . /.-,()*+ 3 V V V V V V V V V V V V V /.-,()*+ps 1 /.-,()*+ps 2 qqqqqq /.-,()*+p− 5 /.-,()*+ps 3 qqqqqq /.-,()*+p− 6 /.-,()*+ps 4 qqqqqq /.-,()*+ps 7 _____ Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â _____ structure µfrom Theorem 5 Fig. 3. Membrane structure for Theorem 7. As in Theorem 5 the initial configuration contains a single string q0in region 3. The system contains sets of rules R1,R2,Rp+ 1, Rp+ 2, Rp+ 3,Rp− 1, Rp− 2, Rp− 3,Rp0 2, Rp0 3 defined as in Theorem 5. There are also following additional rules for instructions p: (WRITE(A), q) (the ruleset R0 3shall be added to R3). R0 3={3.5 :(λ, p, λ;inps 1)e|p∈Qs}, Rps 1={w.1.1 :(λ, M, λ;inps 2)a, w.1.2 :(λ, M, λ;out)e}, Rps 2={w.2.1 :(λ, M0, λ;inps 3)a, w.2.2 :(λ, M0, λ;out)e} ∪ { w.2.3 :(M, x, λ;inps 5)e|x∈O}, Rps 3={w.3.1 :(λ, A, λ;inps 4)a, w.3.2 :(λ, Y, λ;out)a} ∪ { w.3.3 :(x, M, λ;inps 6)e|x∈O\ {M0, q}}, Rps 4={w.4.1 :(λ, q, λ;out)a, w.4.2 :(M0, M, λ;inps 7)e}, Rps 5=∅, Rps 6=∅, Rps 7=∅. We simulate the WRITE instruction as follows. Suppose the configuration of register machine is pAx1 1···Axd dand the word a1···anis written on the output tape. The corresponding simulating string in Πwill be of form p∆w, where w= ∆(Ax1 1· · · Axd dYt)t⊥ a1· · · an,t≥0. After the deletion of the state symbol p, a marker Mis inserted in the string by rule w.1.1. If Mis not inserted at the right end of the string, in the next step rule w.2.3 is applicable and the string enters the trap membrane ps 5. In the next step symbol M0is inserted in the string. If it is not inserted before M, then the string is sent to membrane ps 6by rule w.3.3. Hence, at this moment the contents of membrane ps 3is wM0M. If rule w.3.2 is used, then the string Yt⊥ wreaches membrane 3 and no rule is applicable anymore. Otherwise, P Systems with Minimal Insertion and Deletion 19 symbol Ais inserted by rule w.3.1. If it is not between M0and M, then rule w.4.2 is applicable and the string enters membrane ps 7. After that qis inserted between Aand M, otherwise the trapping rule w.3.3 is applicable. At this moment, the configuration of the system consists of the string wtM0AqM in membrane ps 3. Now if the rule w.3.1 is used, then the string is sent to the trap membrane by rule w.4.1. Otherwise, rule w.3.2 should be used followed by the application of rules w.2.2 and w.1.2, leading to string Yt⊥ wAq in membrane 3. Hence, the symbol A is appended at the end of the string. At the end of the computation, all symbols from O−Tare deleted and a word generated by Mis obtained. Since RE is closed with respect to the mirror operation we obtain: Corollary 3. LSP (ins0,0 1< del0,1 1) = RE. We remark that the contextual deletion was used only to check for erroneous evolutions. Therefore we can replace it by a context-free deletion of two symbols. Theorem 8. LSP∗(ins0,0 1< del0,0 2) = RE. Proof. We modify the proof of Theorem 7 as follows. •Replace rules w.2.3 ((M, x, λ;inps 5)e∈Rps 2) by rules (λ, Mx, λ;inps 5)e, •Replace rules w.3.3 ((M, x, λ;inps 6)e∈Rps 3) by rules (λ, xM, λ;inps 6)e, •Replace rules w.4.2 ((M0, M, λ;inps 7)e∈Rps 4) by rules (λ, M0M, λ;inps 7)e. The role of the new rules is the same as the role of the rules that were replaced. More exactly, the system checks whether two certain symbols are consecutive and if so, the string is blocked in a non-output region. We mention that the counterpart of Theorem 8 obtained by interchanging parameters insertion and deletion rules is not true, see Theorem 2. 5 Conclusions We showed several results concerning P systems with insertion and deletion rules of small size. Surprisingly, systems with context-free rules inserting and deleting only one symbol are quite powerful and generate P sRE if the priority of deletion over insertion is used. From the language generation viewpoint such systems are not too powerful and no language specifying the order of symbols can be generated. To be able to generate more complicated languages we considered systems with one-symbol one-sided insertion or deletion contexts. In both cases we obtained that any recursively enumerable language can be generated. The same result holds if a context-free deletion of two symbols is allowed. The counterpart of the last result is not true, moreover Theorem 2 shows that the insertion of strings of an arbitrary size still cannot lead to generating languages like a∗b∗. We also have considered one-symbol context-free insertion-deletion P systems without the priority relations and we showed that in terms of Parikh sets these 20 A. Alhazov et al. systems characterize the P sMAT family. However, in terms of the generated language such systems are strictly included in MAT . Most of results above were obtained using rules with target indicators. It is interesting to investigate the computational power of systems with non-specific target indicators in or go. Another open problem is to replace the priority relation by some other mechanism without decreasing the computational power. Acknowledgments The first author acknowledges the support of the Japan Society for the Promotion of Science, and the Grant-in-Aid, project 20·08364. The first, the third and the fourth authors acknowledge the support by the Science and Technology Center in Ukraine, project 4032. The third author gratefully acknowledges the support of the European Commission, project MolCIP, MIF1-CT-2006-021666. The second author acknowledges the support PIF program of University Rovira i Virgili, and project no. MTM2007-63422 from the Ministry of Science and Education of Spain. References 1. A. Alhazov, R. Freund, A. Riscos-N´u˜nez: One and two polarizations, membrane creation and objects complexity in P systems. Proc. SYNASC’05, IEEE Computer Society, 2005, 385–394. 2. A. Alhazov, R. Freund, Yu. Rogozhin: Computational power of symport/antiport: History, advances, and open problems. Proc. WMC 2005, Vienna, LNCS 3850, Springer, 2006, 1–30. 3. M. Daley, L. Kari, G. Gloor, R. Siromoney: Circular contextual insertions/deletions with applications to biomolecular computation. Proc. of 6th Int. Symp. on String Processing and Information Retrieval, SPIRE’99, Cancun, 47–54. 4. R. Freund, O.H. Ibarra, Gh. P˘aun, H.-C. Yen: Matrix languages, register machines, vector addition systems. Third Brainstorming Week on Membrane Computing, Sevilla, 2005, 155–168. 5. R. Freund, M. Oswald: GP systems with forbidding context. Fundamenta Informaticae, 49, 1–3 (2002), 81–102. 6. B.S. Galiukschov: Semicontextual grammars. Matematika Logica i Matematika Linguistika, Tallin University, 1981, 38–50 (in Russian). 7. S.A. Greibach: Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7 (1978), 311–324. 8. L. Kari: On Insertion and Deletion in Formal Languages. PhD Thesis, University of Turku, 1991. 9. L. Kari, Gh. P˘aun, G. Thierrin, S. Yu: At the crossroads of DNA computing and formal languages: Characterizing RE using insertion-deletion systems. Proc. DNA Based Computers, 1997, Philadelphia, 318–333. 10. L. Kari, G. Thierrin: Contextual insertion/deletion and computability. Information and Computation, 131, 1 (1996), 47–61. P Systems with Minimal Insertion and Deletion 21 11. A. Krassovitskiy, Yu. Rogozhin, S. Verlan: Further results on insertion-deletion systems with one-sided contexts. Proc. LATA 2008, LNCS 5196, Springer, 2008, 347– 358. 12. A. Krassovitskiy, Yu. Rogozhin, S. Verlan: One-sided insertion and deletion: Traditional and P systems case. Proc. CBM 2008, Vienna, 53–64. 13. A. Krassovitskiy, Yu. Rogozhin, S. Verlan: Computational power of P systems with small size insertion and deletion rules. Proc. CSP 2008, Cork, 137–148. 14. S. Marcus: Contextual grammars. Rev. Roum. Math. Pures Appl., 14 (1969), 1525– 1534. 15. M. Margenstern, Gh. P˘aun, Yu. Rogozhin, S. Verlan: Context-free insertion-seletion Systems. Theoretical Computer Science, 330 (2005), 339–348. 16. C. Martin-Vide, Gh. P˘aun, A. Salomaa: Characterizations of recursively enumerable languages by means of insertion grammars. Theoretical Computer Science, 205, 1–2 (1998), 195–205. 17. A. Matveevici, Yu. Rogozhin, S. Verlan: Insertion-deletion systems with one-sided contexts. LNCS 4664, Springer, 2007, 205–217. 18. M.L.Minsky: Computation. Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, NJ, 1967. 19. Gh. P˘aun: Marcus Contextual Grammars. Kluwer, Dordrecht, 1997. 20. Gh. P˘aun: Membrane Computing. An Introduction. Springer, Berlin, 2002. 21. Gh. P˘aun, G. Rozenberg, A. Salomaa: DNA Computing. New Computing Paradigms. Springer, Berlin, 1998. 22. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. Springer, Berlin, 1997. 23. A. Takahara, T. Yokomori: On the computational power of insertion-deletion systems. Proc. DNA Based Computers 2002, Sapporo, LNCS 2568, Springer, 2003, 269– 280. 24. S. Verlan: On minimal context-free insertion-deletion systems. Journal of Automata, Languages and Combinatorics, 12, 1-2 (2007), 317-328. 25. D.Wood: Theory of Computation. Harper and Row, New York, 1987. A Short Note on Reversibility in P Systems Artiom Alhazov1,2, Kenichi Morita1 1IEC, Department of Information Engineering, Graduate School of Engineering Hiroshima University, Higashi-Hiroshima 739-8527 Japan [email protected] 2Institute of Mathematics and Computer Science Academy of Sciences of Moldova, Academiei 5, Chi¸sin˘au MD-2028 Moldova [email protected] Summary. Membrane computing is a formal framework of distributed parallel computing. In this paper we study the reversibility and maximal parallelism of P systems from the computability point of view. The notions of reversible and strongly reversible systems are considered. The universality is shown for one class and a negative conjecture is stated for a more restricted class of reversible P systems. For one class of strongly reversible P systems, a very strong limitation is found, and it is shown that this limitation does not hold for a less restricted class. 1 Introduction Reversibility is an important property of computational systems. It has been well studied for circuits of logical elements ([3]), circuits of memory elements ([7]), cellular automata ([8]), Turing machines ([1], [10]), register machines ([6]). Reversibility as a syntactical property is closely related to the microscopic reversibility, so it implies that the computation does not increase the entropy of the system, which in turn assume better miniaturization possibilities for potential implementation. A slightly different view on reversible systems is given for type-0 grammars ([9]). The so-called uniquely parsable grammars are studied. In very simple words, this property (still being syntactical) implies that the generation of any word in the language is unique (modulo the order of applying the rules in case when the composition of applying them is commutative). The advantage of having such a property is that it is easier to analyze their behavior. Clearly, this reason remains valid even if the property of reversibility becomes undecidable (just like the property of determinism in certain membrane systems). Moreover, reversibility essentially is backward determinism. Reversible P systems already were considered ([4]), but the model is energy-based (so the parallelism is invariant-driven rather than maximal) and the main result is the simulation of the Fredkin gate (so construction of a universal system in this way would use an 24 A. Alhazov, K. Morita infinite structure). In this paper we focus on the interplay between reversibility and maximal parallelism, from the viewpoint of computability. 2 Definitions In this paper we illustrate the reversibility concepts on P systems with symport/antiport and one membrane, sometimes with inhibitors or priorities. For simplicity, we also assume that the environment contains an unbounded supply of all objects. The system thus can be defined by the alphabet, the initial multiset, the set of rules associated to the membrane, and the set of terminal objects. Throughout this paper we represent multisets by strings. We write an antiport rule sending a multiset xout and bringing a multiset yin as x/y, and the symport case corresponds to y=λ. If a rule has inhibitor a, we write it as x/y|¬a. The priority relationship is denoted by >. It is not difficult to generalize the definitions for the models with multiple membranes and changing membrane structure, but it is not important here. Consider a P system Πwith alphabet O. In our setting, a configuration is defined by the multiset of objects inside the membrane, represented by some string u∈O∗. The space Cof configurations is essentially |O|-dimensional space with non-negative integer coordinates. We use the usual definitions of maximally parallel transition ([11]). It induces an infinite graph of C. Notice that the halting configurations (and only them) have out-degree zero. We call Πstrongly reversible if every configuration has in-degree at most one. We call Πreversible if every reachable configuration has in-degree at most one. A property equivalent to reversibility is determinism of a dual P system ([2]). The result of a halting computation is the number of terminal objects inside the membrane when the system halts. The set N(Π) of numbers generated by a P system Πis the set of results of all its computations. The family of number sets generated by reversible P systems with features αis denoted by NrOP1(α)T, where α⊆ {sym∗, anti∗, inh, Pri}and the braces of the set notation are omitted. Subscript Tmeans that only terminal objects contribute to the result of computations; if T=O, we may omit specifying it in the description and we then also omit the subscript Tin the notation. To bound the weight (i.e., maximal number of objects sent in a direction) of symport or antiport rule, associated ∗is replaced by the actual number. For strong reversible systems, we replace in the notation r by rs. 2.1 Register machines In this paper we consider register machines with increment, unconditional decrement and test instructions, see also [6]. A register machine is a tuple M= (n, Q, q0, qf, I) where A Short Note on Reversibility in P Systems 25 •nis the number of registers; •Iis a set of instructions labeled by elements of Q; •q0∈Qis the initial label; •qf∈Qis the final label. The allowed instructions are: •(q:i?, q0, q00) - jump to instruction q00 if the contents of register iis zero, otherwise proceed to instruction q0; •(q:i+, q0, q00) - add one to the contents of register iand proceed to either instruction q0or q00, non-deterministically; •(q:i−, q0, q00) - subtract one from the contents of register iand proceed to either instruction q0or q00, non-deterministically; •(qf:halt) - finish the computation; it is a unique instruction with label qf. If q0=q00 for every instruction (q:i+, q0, q00 ) and for every instruction (q: i−, q0, q00), then the machine is called deterministic. A register machine is called reversible if for some state qthere is more than one instruction leading to it, then exactly two exist, they test the same register, one leads to qif the register is zero and the other one leads to qif the register is positive. More formally, for any two different instructions (q1:i1α1, q0 1, q00 1) and (q2:i2α2, q0 2, q00 2), it holds that q0 16=q0 2and q00 16=q00 2. Moreover, if q0 1=q00 2or q00 1=q0 2, then α1=α2=? and i1=i2. It has been shown ([6]) that reversible register machines are universal. It follows that non-deterministic reversible register machines can generate any recursively enumerable set of non-negative integers as a value of the first register by all its possible computations starting from all registers having zero value. 3 Examples and Universality We now present a few examples to illustrate the definitions. Example 0: Consider a P system Π0= ({a, b}, a, {a/ab}). It is strongly reversible (for a preimage, remove as many copies of bas there are copies of a, in case it is possible and there is at least one copy of a), but no halting configuration is reachable. Therefore, ∅ ∈ NrsOP1(anti∗). Example 1: Consider a P system Π1= ({a, b, c}, a, {a/ab, a/c}). It generates the set of positive integers and it is reversible (for the preimage, replace cwith aor ab with b), but not strongly reversible (e.g., aa ⇒cc and ac ⇒cc). Hence, N+∈NrOP(anti2). Example 2: Consider a P system Π2= ({a, b}, aa, {aa/ab, ab/bbb}). It is reversible (aa has in-degree 0, while ab and bbb have in-degree 1, and no other configuration is reachable), but not strongly reversible (e.g., aab ⇒abbb and aabb ⇒abbb). 26 A. Alhazov, K. Morita Example 3: Any P system with a rule x/λ,x∈O+, is not reversible. Therefore, symport rules cannot be actually used in a reversible P systems with one membrane. Example 4: Any P system with rules x1/y,x2/y that applied at least one of them in some computation is not reversible. We now show that reversible P systems with either inhibitors or priorities are universal. Theorem 1. NrOP1(anti2, Pri)T=NrOP1(anti2, inh)T=NRE. Proof. We reduce the theorem statement to the claim that such P systems simulate the work of any reversible register machine M= (n, Q, q0, qf, I). Consider a P system Π= (O, q0, R, {r1}),where O={ri|1≤i≤n} ∪ Q, R={q/q0ri, q/q00ri|(q:i+, q0, q00 )∈I} ∪ {qri/q0, qri/q00 |(q:i−, q0, q00)∈I} ∪ Rt, Rt={q/q00|¬ri, qri/q0ri|(q:i?, q0, q00 )∈I}. Inhibitors can be replaced by priorities by redefining Rtas follows. Rt={qri/q0ri> q/q00 |(q:i?, q0, q00 )∈I}. Since there is a bijection between the configurations of Πcontaining one symbol from Qand the configurations of M, the reversibility of Πfollows from the correctness of simulation, the reversibility of M, and from the fact that the number of symbols from Qis preserved by transitions of Π. 4 Limitations The construction in the theorem above uses both cooperation and additional control. It is natural to ask whether both inhibitors and priorities can be avoided. Yet, consider the following situation. Let (p:i?, s, q00 ),(q:i?, q0, s)∈I. It is usual for reversible register machines to have this, since the preimage of configuration sC depends on register i. Nevertheless, P systems with maximal parallelism without additional control can only implement a zero-test by try-and-wait-then-check strategy. In this case, the object containing the information about the register p finds out the result of checking after a possible action of the object related to the register. Therefore, when the state represented in the configuration of the system changes to s, it obtains an erroneous preimage representing state q. This leads to the following Conjecture 1. Reversible P systems without priorities and without inhibitors are not universal. A Short Note on Reversibility in P Systems 27 Now consider a strongly reversible P system. The following theorem establishes a very serious limitation on such systems if no additional control is used. Theorem 2. In strongly reversible P systems without inhibitors and without priorities, every configuration is either halting or induces only infinite computation(s). Proof. If the right-hand side of every rule contains a left-hand side of some rule, then the claim holds. Otherwise, let x/y be a rule of the system such that ydoes not contain the left-hand side of any rule. Then x⇒yand yis a halting configuration. It is not difficult to see that xy ⇒yy (objects yare idle) and xx ⇒yy (the rule can be applied twice). Therefore, such a system is not strongly reversible, which proves the theorem. Therefore, the strongly universal systems without additional control can only generate singletons, i.e., NrsOP1(anti∗)T={{n} | n∈N}, and only in a degenerate way, i.e., without actually computing. It turns out that the theorem above does not hold if inhibitors are used. Consider a system Π3= ({a, b}, a, {a/b|¬b}). If at least one object bis present or no objects aare present, such a configuration is a halting one. Otherwise, all objects aare exchanged by objects b. Therefore, the only possible transitions in the space of all configurations are of the form an⇒bn,n > 1, and the system is strongly reversible. 5 Discussion We outlined the concepts of reversibility and strong reversibility for P systems, concentrating on the case of symport/antiport rules (possibly with control such as priorities or inhibitors) with one membrane, assuming that the environment contains an unbounded supply of all objects. We showed that reversible P systems with control are universal, and we conjectured that this result does not hold without control. Moreover, the strongly reversible P systems without control do not halt unless the starting configuration is halting, but this is no longer true if inhibitors are used. Showing related characterizations might be quite interesting. Many other problems are still open, e.g., reversibility of P systems with active membranes. Acknowledgments Artiom Alhazov gratefully acknowledges the support of the Japan Society for the Promotion of Science and the Grant-in-Aid for Scientific Research, project 20·08364. He also acknowledges the support by the Science and Technology Center in Ukraine, project 4032. 34 B. Aman, G. Ciobanu 2.2 Definition Definition 1. Amutual mobile membrane system with surface objects is a construct Π= (P, µ, w1, . . . , wn, R, iO) where: 1. n≥1(the initial degree of the system); 2. Pis an alphabet of proteins (its elements are called objects); 3. iOis the output membrane; 4. µis a membrane structure, consisting of nmembranes. A membrane structure is a hierarchically arranged set of membranes, where we distinguish the external membrane (usually called the “skin” membrane) and several internal membranes; a membrane without any other membrane inside it is said to be elementary; 5. w1, . . . , wnare strings over V, describing the initial markings of the nmembranes of µ; 6. Ris a finite set of developmental rules, of the following forms: a) [ ]uv [ ]uv0→[[ ]w]w0for u, u, w, w0∈P+;v, v0∈P∗ mutual endocytosis An elementary membrane containing the multiset uv on the membrane enters the adjacent membrane containing the multiset uv0on the membrane; the multisets uv and uv0are transformed into multisets wand w0during the evolution; b) [[ ]uv ]uv0→[ ]uw [ ]uw0,u, u, w, w0∈P+;v, v0∈P∗ mutual exocytosis An elementary membrane containing the multiset uv on the membrane exits the adjacent membrane containing the multiset uv0on the membrane; the multisets uv and uv0are transformed into multisets wand w0during the evolution; c) [ ]uv [ ]uv0→[ ]w[ ]w0,u, u, w, w0∈P+;v, v0∈P∗ mutual contextual evolution The multisets of objects uv and uv0placed on two sibling membranes are transformed into the multisets wand w0. The rules are applied according to the following principles: 1. All rules are applied in parallel, non-deterministically choosing the rules, the membranes, and the objects, but in such a way that the parallelism is maximal; this means that in each step we apply a set of rules such that no further rule can be added to the set. 2. The membrane containing the multiset uon it from the rules of type (a)−(b) is said to be active, while the membrane containing the multiset uon it is said to be passive. In any step of a computation, any object and any active membrane can be involved in at most one rule, but the passive membranes Mutual Mobile Membranes Systems with Surface Objects 35 are not considered involved in the use of the rules (hence they can be used by several rules at the same time as passive membranes). 3. When a membrane is moved across another membrane, by endocytosis or exocytosis, its whole contents (its objects) are moved. 4. If a membrane exits the system (by exocytosis), then its evolution stops. 5. All objects and membranes which do not evolve at a given step (for a given choice of rules which is maximal) are passed unchanged to the next configuration of the system. 3 Competitions We start with an example from [19] which motivates biologically the study of competitions. Example 1. Bacteriophage λis a temperate phage, meaning that it can undergo either a lytic or a lysogenic cycle (see Figure 5). When there is a rich medium available and its host bacterium is growing rapidly, the prophage takes advantage of its favorable cellular environment and remains lysogenic. When the host bacteria are not as healthy, the prophage senses this and, as a survival mechanism, leaves the host chromosome and becomes lytic. The phage makes this decision by means of a “genetic switch”: Two regulatory viral proteins, labeled cI and Cro, compete for two operator/promoter sites on phage DNA. The two operator/promoter sites control the transcription of the viral genes involved in the lytic and the lysogenic cycles, respectively, and the two regulatory proteins have opposite effects on the two operators (Figure 2). Phage infection is essentially a “race” between these two regulatory proteins. In a healthy E. coli host cell, Cro synthesis is low, so cI “wins” and the phage enters a lysogenic cycle. If the host cell is damaged by mutagens or other stress, Cro synthesis is high, promoters for phage DNA and viral coat proteins are activated, and bacterial lysis ensues. Remark 1. Rarely, two viruses infect a cell at the same time. This is an unusual event, as once an infection cycle is under way, there is usually not enough time for an additional infection. In addition, an early protein prevents further infections in some cases. In this case the protein is the one who prevents further races inside the infected cell. In concurrency, a competition occurs when more than one rule are engaged for the same resources. Here is an example: Example 2. Suppose at a given moment of computation we have a membrane containing the multiset of objects aa and two rules: aa →band aa →c. We observe that the rules have similar left objects. The application of one of the rules blocks the application of the other rule. 36 B. Aman, G. Ciobanu Fig. 5. The Lytic and Lysogenic Cycles of Bacteriophage: Infection by viral DNA leads to the multiplication of the virus and lysis of the host bacterial cell. In the lysogenic cycle, an inactive prophage is replicated as part of the host’s chromosome. This kind of competitions are called resource competitions. Such a competition occurs when two rules try to use at least one common resource. Resource competitions are desirable in membrane computing for simulating non-deterministic behaviors. In mutual mobile membranes we also find a different form of competition, namely the location competition. Consider the following example: Example 3. Suppose at a given moment of the computation we have the following membrane configuration: [ ][ ]a[ ]b, and two rules: [ ][ ]a→[[ ]c] and [ ][ ]b→[[ ]d]. We observe that membrane containing ais included in the left part of both rules. We have two possible evolutions: •If we first apply the rule [ ][ ]a→[[ ]c], we obtain the membrane structure [[ ]c][ ]band the other rule cannot be applied anymore. •If we first apply the rule [ ][ ]b→[[ ]d] we obtain the membrane structure [ ][[ ]d]aand the other rule cannot be applied since now membrane nis not elementary. We refer to the rules of mobile membrane systems in which only elementary membranes can pass through other membranes [12]. The choice of which rule is applied first makes the other rule useless, so the system should be described initially with only one of these rules, depending on the expected evolution. Mutual Mobile Membranes Systems with Surface Objects 37 Fig. 6. Control of Phage λLysis and Lysogeny: Cro and cI compete for the operator/promoter sites controlling the gene transcription for viral lysis and lysogeny. The movement in mutual mobile membrane systems is local, namely a membrane can only interact with neighboring membranes. Locality of movement implies that a membrane written to accomplish a certain task in a given membrane, it shall not work correctly in another membrane. The location competition raises some problem: 1. it is difficult to describe membrane systems which behave as expected in all contexts; 2. it is difficult to prove behavioral properties of membrane systems. The rules of mobile membranes allow a membrane to enter, or to exit another membrane. The second membrane just undergoes the action, meaning that it has no control on when the movement takes place. As a consequence, it is hard to control the resources inside a given membrane. By defining mutual mobile membranes this is rectified: any movement takes place only if both participants agree. This is achieved by using objects and co-objects to control the movement. The inspiration comes from biology where we have receptors and co-receptors which 38 B. Aman, G. Ciobanu control the interaction between membranes. Location competitions also exist in mutual mobile membranes, but they are easier to detect. 4 Conclusion In the area of membrane computing the authors usually consider that a system is synchronous if the rules are applied in a maximally parallel manner, otherwise it is asynchronous. On the other hand, in process algebra the authors consider that two processes are synchronized if they interact by using actions and co-actions. We adapt the second approach to membrane systems, by replacing the actions and co-actions with objects and co-objects. As related work we can mention [13] and [14] where the authors study the plain and grave interferences which appear in mobile ambients, and try to remove them by defining safe mobile ambients and an appropriate type system. The work presented in this paper corresponds to the first step described in their work, more exactly we define the competitions in mutual mobile membranes. Further work will include the use of a type system for mutual mobile membranes in order to limit the competitions which appear during the evolution of a membrane system. Regarding the asynchronous aspects, we define in [4] a compositional asynchronous membrane system based on a handshake mechanism implemented by using antiport rules and promoters. Such a system is used to evaluate arithmetical expressions starting from simple membranes for addition, subtraction, multiplication and division. References 1. B. Aman, G. Ciobanu: Structural properties and observability in membrane systems. SYNASC, IEEE Computer Society, 2007, 74–84. 2. B. Aman, G. Ciobanu: Membrane systems with surface objects. Proceedings of the International Workshop on Computing with Biomolecules (CBM 2008), 2008, 17–29. 3. C. Bodei, A. Bracciali, D. Chiarugi: Control flow analysis for brane calculi. Electronic Notes in Theoretical Computer Science, 227 (2009), 59–75. 4. C. Bonchis, C. Izbasa, G. Ciobanu: Compositional asynchronous membrane systems. Progress in Natural Science, 17, 4 (2007), 411–416. 5. R. Brijder, M. Cavaliere, A. Riscos-N´u˜nez, G. Rozenberg, D. Sburlan: Membrane systems with marked membranes. Electronic Notes in Theoretical Computer Science, 171, 2 (2007), 25–36. 6. N. Busi: On the computational power of the mate/bud/drip brane calculus: Interleaving vs. maximal parallelism. Workshop on Membrane Computing, LNCS 3850, Springer, 2006, 144–158. 7. N. Busi, R. Gorrieri: On the computational power of Brane calculi. Third Workshop on Computational Methods in Systems Biology, 2005, 106–117. 8. L. Cardelli: Brane calculi. Interactions of biological membranes. Lecture Notes in BioInformatics, 3082, Springer, 2004, 257–278. Mutual Mobile Membranes Systems with Surface Objects 39 9. L.Cardelli, Gh. P˘aun: An universality result for a (mem)brane calculus based on mate/drip operations. ESF Exploratory Workshop on Cellular Computing (Complexity Aspects), Sevilla, 2005, 75–94. 10. M. Cavaliere, S. Sedwards: Membrane systems with peripherial proteins: Transport and evolution. Electronic Notes in Theoretical Computer Science, 171, 2 (2007), 37– 53. 11. S.N. Krishna: Universality results for P systems based on brane calculi operations. Theoretical Computer Science, 371 (2007), 83–105. 12. S.N. Krishna, Gh. P˘aun: P systems with mobile membranes. Natural Computing, 4, 3 (2005), 255–274. 13. F. Levi, D. Sangiorgi: Controlling interference in ambients. Principles of Programming Languages, 2000, 352–364. 14. F. Levi, D. Sangiorgi: Mobile safe ambients. Transactions on Programming Languages and Systems, 25, 1 (2003), 1–69,. 15. R. Milner: Communicating and Mobile Systems: The pi-calculus. Cambridge University Press, 1999. 16. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 17. Gh. P˘aun: Membrane Computing. An Introduction. Springer, 2002. 18. Gh. P˘aun: Membrane computing and brane calculi (Some personal notes). Electronic Notes in Theoretical Computer Science, 171 (2007), 3–10. 19. W.K. Purves, D. Sadava, G.H. Orians, H.C. Heller: Life: The Science of Biology, 7th Edition, W.H. Freeman & Co, 2004. 20. A. Vitale, G. Mauri, C. Zandron: Simulation of a bounded symport antiport P system with brane calculi. BioSytems, 91, 3 (2008), 558–571. Communication and Stochastic Processes in Some Bacterial Populations: Significance for Membrane Computing Ioan I. Ardelean Institute of Biology of the Romanian Academy Centre of Microbiology Splaiul Independentei 296, Bucharest, Romania [email protected] Summary. Intercellular communication between bacterial cells belonging to the same population is well documented in Microbiology, sporulation and cannibalism in B. Subtilis and genetic competence and fratricide in S. pneumoniae being deeply studied in the last years. The investigation of individual cell behavior has revealed that populations of these bacteria sometimes bifurcate into phenotypically distinct, but genetically identical, subpopulations by random switching mechanisms. The probabilistic nature of the random switching mechanisms, the occurrence of some biochemical processes related to it at plasma membrane and the need to study the processes at the level of each individual cell make intercellular communication and stochastic processes very suitable to be modeled by P systems. Motto: But a system which has spherical symmetry, and whose state is changing because of chemical reactions and diffusion, will remain spherically symmetrical for ever.(...) It certainly cannot result in an organism such a horse, which is not spherically symmetrical. [Turing, 1952] 1 Introduction The concept of intercellular communication within a bacterial population belonging to the same species originates in the discovery of genetic competence in Streptococcus pneumoniae (1965) and of quorum sensing (1970) in Vibrio (Bassler and Losick, 2006). In the last decades, with special emphasis in the last years intercellular communication within a bacterial population started to be deeply documented in such a copious way that the scientific community started to introduce within their scientific language expressions such as “bacterially speaking”, competence and “fratricide”, “sporulation and cannibalism” (Bassler and Losick, 2006; Dubnau and Losick, 2006; Claverys and Havarstein, 2007) whereas few scientists put 42 I.I. Ardelean forward and claim that bacterial communication includes assignment of contextual meaning and sentences (semantic/syntax functions) and conduction of “dialogue” – the fundamental aspects of linguistic communication (Ben Jacob et al., 2006, and citations herein), the same authors seeking for the foundation of cognition in bacteria (Ben Jacob et al., 2006). (It is to be noticed that for dialogue the authors used the commas, whereas for cognition they did not.) In this short report we focus on some of these new research on intercellular communication within a bacterial population because: •Communication and stochastic processes become more deeply known when they started to be studied at the level of individual bacterial cell, trend belonging to the so-called single cell microbiology (SCM) which opens a new vision on bacterial world (Brehm-Stecher and Johnson, 2004; Kearns and Losick, 2005; Claverys and Havarstein, 2007); furthermore it was put forward that P systems could become a specific tool to study single bacterial cells as each cell contain a relative small number of important signalling molecules whose behavior could be better described by a discrete systems than by a continuous one (Ardelean, 2006). •SCM investigation by improved techniques has revealed that populations of certain bacteria sometimes bifurcate into phenotypically distinct, but genetically identical, subpopulations, bifurcation which is called bistability (Dubnau and Losick, 2006). The need to study the processes in the each individual cell was originally put forward by Turing (Turing, 1952) who wrote: “To find the rate of change due to chemical reactions only needs to know the concentration of all morphogens at that moment in the one cell concerned” (my underline), a suggestion largely ignored (forgotten?) for decades. •Bistability in our opinion could be appropriately modeled by P systems because of their probabilistic nature of the processes occurring within plasma membrane (as well as in a bulk phase). •Bistability is a random mechanism that switches on different genetic programmes within identical bacteria grown under the same conditions (Dubnau and Losick, 2006). This passage from homogeneity to heterogeneity, this bifurcation both at the level of biochemical reaction and at the level of cell population remembers the bifurcation of chemical reaction (starting from o homogenous medium) mathematically first demonstrated by Turing in his interdisciplinary scientific paper on chemical basis of morphogenesis (Turing, 1952). This type of bifurcation named by Prigogine “Turing bifurcation” (Prigogine, 1977) is one of the tools used by Prigogine (Nobel Prize 1977) to physically explain how biological life (an anti-entropic process) is physically possible in an Universe whose overall entropy is under increase. Communication in Some Bacterial Populations 43 2 Communication and Stochastic Processes in Some Bacterial Populations The recent advent of techniques like flow cytometry and fluorescence microscopy that facilitate the investigation of individual cell behavior has revealed that populations of certain bacteria sometimes bifurcate into phenotypically distinct, but genetically identical, subpopulations by random switching mechanisms. This bifurcation of genetically identical bacterial populations, also called clonal populations exhibit (unimodal) variation in the expression of a given gene, due to random fluctuations in the rates of synthesis and degradation of the cognate gene product, which is referred to as ’noise’ and we will employ this usage. Sometimes, the noise gives rise to another type of variation that is non-unimodal, meaning that the population bifurcates into subpopulations, phenotypic phenomenon known as ’bistability’ (Dubnau and Losick, 2006). For example, when Bacillus Subtilis cells encounter conditions of nutrient deprivation or reach a critical cell density, the cell can choose between two type of bifurcation involving entirely different genetic programmes, according to culture conditions. They can fully induce motility and enter stationary growth, enter sporulation, which cumulates in the formation of an enduring spore or enter the state of competence, in which they are able to take up DNA from the environment for integration into their chromosome via homologous recombination. Both programmes, competence and sporulation, involve the formation of a bistable culture; about 20% of cells will become competent, or a maximum of 80% of the cells will initiate sporulation. The remaining 80% or 20% of the cells, respectively, simply enter stationary phase and, in the case of sporulation, are even killed by the sporulating cells, which secrete a specific toxin, to serve as a nutrient source (Gonzalez-Pastor et al., 2003). Thus, even though all cells encounter identical culture conditions, only a (relatively well-defined) subpopulation fully throws the switch towards the new mode of development. Nevertheless, the non-competent or non-sporulating cells can switch to a new developmental state at a later time (Graumann, 2006). It could be important from P systems the fact that bistability arise stochastically in populations of genetically identical cells, grown in homogeneous and theoretically identical environments (e.g. in liquid media in well-stirred flasks), the choice of which individual cells exhibit altered gene expression being random (Dubnau and Losick, 2006). So far, there are several examples communication and stochastic processes in some bacterial populations but for the sick of simplicity in this paper we will briefly focus only on two of them which involve bistability: sporulation and cannibalism in B. Subtilis and genetic competence and fratricide in S. pneumoniae. 2.1 Sporulation and cannibalism When the nutrients are limited many types of bacteria including B. subtilis entry into sporulation, an elaborate developmental process that culminates in the formation of a specialized cell called spore or endospore. The spore is a dormant cell P Systems with Endosomes Roberto Barbuti, Giulio Caravagna, Andrea Maggiolo–Schettini, Paolo Milazzo Dipartimento di Informatica, Universit`a di Pisa Largo Pontecorvo 3, 56127 Pisa, Italy. {barbuti,caravagn,maggiolo,milazzo}@di.unipi.it Summary. P Systems are computing devices inspired by the structure and the functioning of a living cell. A P System consists of a hierarchy of membranes, each of them containing a multiset of objects, a set of evolution rules, and possibly other membranes. Evolution rules are applied to the objects of the same membrane with maximal parallelism. In this paper we present an extension of P Systems, called P Systems with Endosomes (PE Systems), in which endosomes can be explicitly modeled. We show that PE Systems are universal even if only the simplest form of evolution rules is considered, and we give one application examples. 1 Introduction P Systems were introduced by Pˇaun in [10] as distributed parallel computing devices inspired by the structure and the functioning of a living cell. A P System consists of a hierarchy of membranes, each of them containing a multiset of objects, representing molecules, a set of evolution rules, representing chemical reactions, and possibly other membranes. For each evolution rule there are two multisets of objects, describing the reactants and the products of the chemical reaction. A rule in a membrane can be applied only to objects in the same membrane. Some objects produced by the rule remain in the same membrane, others are sent out of the membrane, others are sent into the inner membranes, which are identified by their labels. Evolution rules are applied with maximal parallelism, meaning that it cannot happen that some evolution rule is not applied when the objects needed for its triggering are available. Many variants and extensions of P Systems exist that include features to increase their expressiveness and that are based on different evolution strategies. Among the most common extensions we mention P Systems with dissolution rules that allow a membrane to disappear and release in the environment all the objects it contains. We mention also P Systems with priorities, in which a priority relationship exists among the evolution rules of each membrane and can influence the applicability of such rules, and P Systems with promoters and inhibitors, in 52 R. Barbuti et al. which the applicability of evolution rules depends on the presence of at least one occurrence and on the absence, respectively, of a specific object. See [2, 11] for the definition of these (and other) variants of P Systems and [13] for a complete list of references to the bibliography of P Systems. In this paper we present another extension of P Systems, called P Systems with Endosomes (PE Systems), with these features: •objects can be contained both inside and on the surfaces of the membranes (as in P Systems with peripheral proteins [5, 9]); •rules are contained on the surfaces of the membranes (they can rewrite objects outside/on/into the membranes); •endosomes can be explicitly created in order to model a biologically inspired transportation mechanism. The definition of this extension of P Systems has a biological inspiration. In fact, the endocytosis of macromolecules is the process by which cells absorb material (molecules such as proteins) from outside the cell by engulfing it with their cell membrane. It is used by all cells of the body because most substances important to them are large polar molecules that cannot pass through the hydrophobic plasma membrane or cell membrane. There exist three kind of endocytosis: phagocytosis, pinocytosis and receptor–mediated endocytosis. In particular, phagocytosis (literally, cell–eating) is the process by which cells ingest large objects, such as cells which have undergone apoptosis, bacteria, or viruses. The membrane folds around the object, and the object is sealed off into a large vacuole known as a phagosome. Pinocytosis (literally, cell–drinking) is concerned with the uptake of solutes and single molecules such as proteins, and, finally, receptor–mediated endocytosis is a more specific active event where the cytoplasm membrane folds inward to form coated pits. These inward budding vesicles bud to form cytoplasmic vesicles. Figure 11summarizes the kinds of endocytosis. By the point of view of the modeler, these three processes are made possible by vesicles (in fact this transportation mechanism is known as vesicle–mediated transportation) which, in the most general case, engulf the macromolecules together with molecules from the surface of the membranes (i.e. receptors). This leads to the creation of endosomes containing the engulfed molecules. The endosomes transfer their content inside the cell by possibly interacting with other components. The endosomes could also be degraded by the interaction with the lysosomes. We define an extension of P Systems (PE Systems) which can explicitly model the creation of endosomes and their interaction inside the cells and, consequently, can easily model these three kind of endocytosis. This variant of P Systems, together with other modeling features such as the modeling of exocytosis (the biologically counterpart of endocytosis), and enriched with channel–mediated communication [1], would provide a powerful and complete modeling language for naturally describing transportation mechanism of molecules inside cells. 1Pictures taken from http://cellbiology.med.unsw.edu.au/units/science/lecture0806.htm P Systems with Endosomes 53 Fig. 1. Three kind of endocytosis: phagocytosis,pinocytosis and receptor–mediated endocytosis. We show that PE Systems are universal even if only the simplest form of evolution rules is considered, namely non–cooperative rules. Finally, we give one application examples to show that endosomes can ease the description of biological systems when PE Systems are used as a modeling formalism. 2 P Systems with Endosomes In this section we recall the definition of standard P Systems, and then we define their extension with endosomes. We will denote multisets over a finite alphabet as strings of alphabet symbols. More precisely, let V∗be the set of all strings over an alphabet V, including the empty one, denoted by λ. For a∈Vand xin V∗ we denote by |x|athe number of occurrences of ain x. If V={a1,...,an}(the ordering is important here), then the Parikh mapping of xis defined by ΨV(x) = (|x|a1,...,|x|an). The definition is extended in the natural way to languages. A string xrepresents the multiset over Vwith the multiplicities of objects a1,...,an as given by ΨV(x). 2.1 P Systems A P System consists of a hierarchy of membranes that do not intersect, with a distinguishable membrane, called the skin membrane, surrounding them all. As usual, we assume membranes to be labeled by natural numbers. Given a set of objects V, a membrane mcontains a multiset of objects in V∗, a set of evolution rules, and possibly other membranes, called child membranes (mis also called the parent of its child membranes). Objects represent molecules swimming in a 54 R. Barbuti et al. chemical solution, and evolution rules represent chemical reactions that may occur inside the membrane containing them. For each evolution rule there is a multiset of objects representing the reactants, and a multiset of objects representing the products of the chemical reaction. A rule in a membrane mcan be applied only to objects in m, meaning that the reactants should be precisely in m, and not in its child membranes. The rule must contain target indications, specifying the membranes where the new objects produced by applying the rule are sent. The new objects either remain in m, or can be sent out of m, or can be sent into one of its child membranes, precisely identified by its label. Formally, the products of a rule are denoted with a multiset of messages of the forms: •(v, here), meaning that the multiset of objects vproduced by the rule remain in the same membrane m; •(v, out), meaning that the multiset of objects vproduced by the rule are sent out of m; •(v, inl), meaning that the multiset of objects vproduced by the rule are sent into the child membrane l. Let TAR be the set of message targets {here, out} ∪ {ini|i∈N}. Given a set of objects Owe denote with Otar the corresponding set of messages O×TAR. As a consequence, we denote with Vtar the set of all messages and we can define an evolution rule as a rule u→vsuch that u∈V∗and v∈V∗ tar. The size of the left–hand side uof an evolution rule is also called the radius of such a rule. If a P System contains rules of radius greater than one, then it is called a cooperative system. Otherwise, it is called non–cooperative. Application of evolution rules is done with maximal parallelism, namely at each evolution step a multiset of instances of evolution rules is chosen non– deterministically such that no other rule can be applied to the system obtained by removing all the objects necessary to apply all the chosen rules. A P System has a tree–structure in which the skin membrane is the root and the membranes containing no other membranes are the leaves. We assume membranes labels to be unique. A membrane structure can be represented as a balanced sequence of labeled brackets and, graphically, as a Venn diagram. Definition 1. AP System is a tuple (V, µ, w1,...,wn, R1,...,Rn)where: •Vis a finite alphabet whose elements are called objects; •µ⊂N×Nis a membrane structure, such that (i, j)∈µdenotes that the membrane labeled by jis contained in the membrane labeled by i; •wiwith 1≤i≤nare strings from V∗representing multisets over Vassociated with the membranes 1,2,...,n of µ; •Riwith 1≤i≤nare finite sets of evolution rules associated with the membranes 1,2,...,n of µ; A sequence of transitions between configurations of a given P System Πis called acomputation. A computation is successful if and only if it reaches a configuration in which no rule is applicable. The result of a successful computation is the multiset P Systems with Endosomes 55 1 EDa →(ED, here)(aa, in2) aD →(#, here) F Da →(F D, here)(a, out) 2 E→(G, here)(ED, in2) #→(#, here) a EDa →(ED, here)(a, out) aD →(#, out) E→(G, here)(F D, out) E→(G, here)(ED, out) GD →λ ED GD →λ Fig. 2. Example of P System that computes {a2n|n∈N}. of objects sent out of the skin membrane during the computation. Unsuccessful computations (computations which never halt) yield no result. Given a P System Πwhose set of object is V, the result x∈V∗of a computation of Πcan be represented as the vector of natural numbers ΦV(x). The set of all vectors of natural numbers computed by Πis denoted Ps(Π). In Fig. 2 we show an example of P System Π1computing {a2n|n∈N}, namely such that P s(Π1) = {2n|n∈N}. Initially, only in membrane 2 there are rules which are applicable and send either objects Fand Dor objects Eand Dinto membrane 1. In the former case the object ain membrane 1 is sent out and the computation halts. In the latter case object ain membrane 1 is consumed and two occurrences of aare sent into membrane 2. Subsequently, Eis consumed and sent into membrane 2 together with D. Note that the rule which sends ED into membrane 2 cannot be applied while there are still objects ain membrane 1, otherwise by the maximal parallelism also the rule producing # would be applied giving rise to an infinite (unsuccessful) computation. Objects asent into membrane 2 are then sent back into membrane 1. The process of doubling and sending into membrane 2 we have explained, could be repeated an arbitrary number of times. Note that all the rules consuming aact on a single occurrence of aat a time and hence the time complexity of the computation is proportional to 2n+2. 2.2 Extension with Endosomes In this section we formally define P Systems with endosomes (PE Systems). To this extent, we start by assuming the same membrane structure µof a P System. As regards objects, similarly to P Systems with peripheral proteins [5, 9], we assume that objects can be contained inside a membrane (as in classical P Systems) and on the surface of a membrane. In order to qualify a position of an object with respect to a membrane, we use in to identify the object inside the membrane, out to identify the object outside the membrane and here to identify the object on the surface of the membrane. Let T AR be the set of message targets {in, out, here}; given a set of objects Owe denote with Otar the corresponding set of messages O×TAR, and we denote with Vtar the set of all messages. 56 R. Barbuti et al. We can now introduce the evolution rules of PE Systems; rules are conceptually divided in evolutionary rules (in the same sense of P Systems) and rules for the creation of endosomes. We recall that, differently from P Systems, the rules of PE Systems are conceptually associated with the surfaces of the membranes of the system. The former class of rules are of the form u→vwhere u∈V+ tar and v∈V∗ tar. The definition of cooperative and non–cooperative rules are the same as for P Systems. Notice that this format for evolutionary rules, which are syntactically different from those of P Systems, may seem to be less expressive than the one of P Systems, in particular for rule moving objects into specific membranes (communication rules). In order to show that this is not the case, let us assume an hypothetical membrane structure µsuch that (l, l′)∈µ, namely a membrane structure in which l′is nested into l. In order to give a rule which moves an object inside membrane l′we cannot use the identifier inl′in a rule of the surface of the membrane l(as in P Systems) because we cannot use the identifier l′as subscript to in. However, the same behavior can be obtained by replacing the rule u→(v, inl′) in the membrane l, as in usual P Systesm, with the PE System rule (u, out)→(v, in) on the surface of the membrane l′. The behavior modeled by this rule, which is in some sense an “attraction” by the nested membrane rather than the “sending” from the top membrane, leads to result analogous to those obtained by P Systems, namely to the transportation of the object inside the nested membranes. The rules for creating endosomes are of the form endoE(u∈V∗, v ∈V∗) where: •Eis a set of evolutionary rules for the endosome; •uis the multiset of objects that must appear on the surface of the membrane containing the rule; •vis the multiset of objects that must appear outside the membrane containing the rule. Notice that each endosome has got its own evolutionary rules in set E. These rules model the behavior of the endosome. As regards the creation of an endosome, it is necessary that objects in uare present on the surface of the membranes (in some sense they can be seen as the receptors) and that objects in vare present outside of the membrane creating the endosome (in some sense they can be seen as the molecules to be engulfed). More formally, the applicability of the endosome rule is possible in the following general case: let (j, i)∈µand let endoE(u, v) be a rule belonging to the surface of the membrane i, than it can be applied only if uis a submultiset of the objects contained on the surface of the membrane i, and only if vis a submultiset of the objects contained inside the membrane j. The result of the application of such a rule is a creation of an endosome inside membrane i containing uon its surface and containing vinside. The endosome itself behaves like a membrane having on its surface rules E. We can now formally define a PE System as follows. Definition 2. APE System is a tuple (V, µ, w1,...,wn, z1,...,zn, R1,...,Rn) where: P Systems with Endosomes 57 •Vis an alphabet whose elements are called objects; •µ⊂N×Nis a membrane structure, such that (i, j)∈µdenotes that the membrane labeled by jis contained in the membrane labeled by i; •wiwith 1≤i≤nare strings from V∗representing multisets over Vassociated with the content of membranes 1,2,...,n of µ; •ziwith 1≤i≤nare strings from V∗representing multisets over Vassociated with the surfaces of membranes 1,2,...,n of µ; •Riwith 1≤i≤nare finite sets of evolution rules associated with the surfaces of the membranes 1,2, . . . , n of µ. The notions of (successful) computation and of result of computations of PE Systems are the same as for standard P Systems. 3 Universality of PE Systems In this section we prove a universality result for PE Systems by showing that any matrix grammar with appearance checking can be simulated by a PE System. As a consequence, before giving the result and its proof, we recall from [11] the definition of such variant of matrix grammars and some related notions. 3.1 Matrix grammars with appearance checking A (context-free) matrix grammar with appearance checking is a tuple G= (N, T, S, M, F ), where Nand Tare disjoint alphabets of non–terminals and terminals, respectively, S∈Nis the axiom, Mis a finite set of matrices, namely sequences of the form (A1→x1,...,An→xn) of context–free rules over N∪T with n≥1, and Fis a set of occurrences of rules in the matrices of M. For a string w, a matrix m: (r1,...rn) can be executed by applying its rules to wsequentially in the order in which the appear in m. Rules of a matrix occurring in Fcan be skipped during the execution of the matrix if they cannot be applied, namely if the symbol in their left–hand side is not present in the string. Formally, given w, z ∈(N∪T)∗, we write w=⇒zif there is a matrix (A1→ x1,...,An→xn) in Mand the strings wi∈(N∪T)∗with 1 ≤i≤n+ 1 such that w=w1,z=wn+1 and, for all 1 ≤i≤n, either (1) wi=w′ iAiw′′ iand wi+1 =w′ ixiw′′ i, for some w′ i, w′′ i∈(N∪T)∗, or (2) wi=wi+1,Aidoes not appear in wiand the rule Ai→xiappears in F. We remark that Fconsists of occurrences of rules in M, that is, if the same rule appears several times in the matrices, it is possible that only some of these occurrences are contained in F. The language generated by a matrix grammar with appearance checking Gis defined as L(G) = {w∈T∗|S=⇒∗w}, where =⇒∗wis the reflexive and transitive closure of =⇒. The family of languages of this form is denoted by MAT λ ac, when rules having the empty string λas right hand side (λ–rules) are allowed, and 58 R. Barbuti et al. by MATac when such rules are not allowed. Moreover, the family of languages generated by matrix grammars without appearance checking (i.e. with F=∅) is denoted by MAT λ, when λ–rules are allowed, and by MAT , when such rules are not allowed. It is known that (i) MAT ⊂MATac ⊂CS; (ii) MAT λ⊂MATλ ac =RE, where CS and RE are the families of languages generated by context–sensitive and arbitrary grammars, respectively. Let ac(G) be the cardinality of Fin Gand let |x|denote the length of the string x. A matrix grammar with appearance checking G= (N, T, S, M, F ) is said to be in the strong binary normal form if N=N1∪N2∪ {S, #}, with these sets mutually disjoint, and the matrices in Mare in one of the following forms: 1. (S→XA), with X∈N1, A ∈N2; 2. (X→Y, A →x), with X, Y ∈N1, A ∈N2, x ∈(N2∪T)∗,|x| ≤ 2; 3. (X→Y, A →#), with X, Y ∈N1, A ∈N2; 4. (X→λ, A →x), with X∈N1, A ∈N2, x ∈T∗,|x| ≤ 2. Moreover, there is only one matrix of type 1, Fconsists exactly of all rules A→# appearing in matrices of type 3 and ac(G)≤2. We remark that # is a trap symbol, namely once introduced it cannot be removed, and a matrix of type 4 is used only once, in the last step of a derivation. For each matrix grammar (with or without appearance checking) there exists an equivalent matrix grammar in the strong binary normal form. Consequently, for each language L∈RE there exists a matrix grammar with appearance checking Gsatisfying the strong binary normal form and such that L(G) = L. Conventions A matrix grammar with appearance checking in the strong binary normal form is always given as G= (N, T, S, M, F ), with N=N1∪N2∪ {S, #}and with n+ 1 matrices in M, injectively labeled with m0, m1,...,mn. The matrix m0: (S→XinitAinit) is the initial one, with Xinit a given symbol from N1and Ainit a given symbol from N2; the next kmatrices are without appearance checking rules, mi: (X→α, A →x), with 1 ≤i≤k, where X∈N1, α ∈N1∪ {λ}, A ∈ N2, x ∈(N2∪T)∗,|x| ≤ 2 (if α=λ, then x∈T∗); the last n−kmatrices have rules to be applied in the appearance checking mode, mi: (X→Y, A →#), with k+ 1 ≤i≤n, X, Y ∈N1, and A∈N2. Since the grammar is in the strong binary normal form, we have (at most) two symbols B(1) and B(2) in N2such that the rules B(j)→# appear in matrices miwith k+ 1 ≤i≤n. For j∈ {1,2}, we denote with ℓjthe set {i|the matix micontains the rule B(j)→#}. For uniformity, we also denote ℓ0={1,2,...,k}and ℓ=ℓ0∪ℓ1∪ℓ2={1,2,...,n}(note that 0 6∈ ℓ). Clearly, the sets ℓ0, ℓ1and ℓ2are disjoint. We remark that in matrix grammars in strong binary normal forms we can assume that all symbols X∈N1appear as the left-hand side of a rule from a matrix: otherwise, the derivation is blocked after introducing such a symbol, hence we can remove these symbols and the matrices involving them. P Systems with Endosomes 59 3.2 Universality We prove that PMC Systems are universal by showing that the family, denoted PsE2(ncoo), of sets P s(Πe) of results computed by PE Systems with at least two membranes and with non–cooperative rules is equivalent to the family, denoted PsRE, of the images of all the languages in RE obtained through the Parikh mapping (this is the family of recursively enumerable sets of vectors of natural numbers). As P Systems with non-cooperative rules are not universal, our result implies that universality is due to the presence of endosomes. Theorem 1. PsE2(ncoo) = P sRE. Proof. It is enough to show that for a Gin strong binary normal form there is a PE System ΠGsuch that P s(ΠG) = ΨT(L(G)). We assume that the output of this PE System is given by the objects sent out from the skin membrane. The alphabet we take into consideration is given by T∪N1∪N2∪ {c} ∪ {ci, di, d′ i|i= 1,2}. We build ΠGas a system with a root membrane, labeled 1, and one child membrane labeled 2. All the objects encoding the grammar will be stored inside membrane 1 and the matrixes will be simulated by membrane 2. The initial configuration is given by the objects corresponding to Xinit and Ainit contained in membrane 1, namely objects of w1, and by the token ccontained on the surface of membrane 2, namely z2={c}. This PE System works as follows: it has a cyclic behavior such that, at the beginning of the cycle, at most one endosome in membrane 2 can be created and, if possible, all terminal symbols inside membrane 1 are sent out as output symbols. The created endosome can start a series of steps resulting in the interpretation of the application of a matrix or, differently, it can start a checking phase to model the fact that, if there exist non terminal symbols which cannot be rewritten by any grammar, than the computation has not to halt. In the case in which it starts the interpretation of a matrix of type 2 or 4 (a matrix miwith 1 ≤ i≤k), the involved non terminals are taken by the endosome which contains as rules the ones interpreting the matrix. Objects will be sent into membrane 2 by these rules creating the result of applying the corresponding matrix to the non terminals. Subsequently, these objects are sent out to membrane 1 to restart the cyclic behavior. We recall that during this process no other endosomes can be created, so no other matrixes can be simulated. Differently, in the case in which a matrix of type 3 (a matrix miwith k+1 ≤i≤n) is applied, the single non terminal of N1is taken into the endosome. The endosome will work in the same sense of the endosomes interpreting matrixes of type 2 and 4 even though, at the end of the application of this matrix, instead of restarting with the cyclic behavior, a checking process is started. This process checks, by creating endosomes, the presence of the proper non terminal symbol B(j). If this symbol is found, a special endosome is created which will introduce a trap symbol in this PE System so that the computation will not halt. Analogously, if it is not found, an endosome will restore the configuration of this PE System so that the cyclic behavior can start again. 66 M. Cardona et al. The P system presented in [1] gives good results in order to study the evolution of the ecosystem based on the Bearded Vulture in the Catalan Pyrenees, but it does not take into account important factors such as the population density or the feeding limitations. In the Catalan Pyrenees, in the North-east of Spain, three vulture species inhabits sharing the geographic space and the existent food resources so in this work, we present a P system for modelling an ecosystem based on three vulture species and the prey species present from which scavengers obtain their food. The present model improves the results presented in [1]. Apart from adding two new predator species (the Egyptian Vulture Neophron percnopterus and Eurasian Griffon Vulture Gyps fulvus), we introduce new prey species (making a total of 12 species) in the new model that provide feeding resources for the scavenger community. Besides, new rules are introduced to limit the maximum amount of animals that can be supported by the ecosystem as well as the amount of grass available for the herbivorous species. For a good and efficient management of the ecosystems, it is necessary to know the quantity and the evolution of the biomass that reaches every species. One of the contributions the P system presents is the evolution of the quantity of annual biomass that is left by every species. The paper is organized as follows: First, an ecosystem, which is located in the Catalan Pyrenees and is to be modelled, is described. Section 3 shows a formal framework to model ecosystems by means of probabilistic P systems, and a P system modelling the above mentioned ecosystem is presented. In Section 4, we discuss the results obtained and we compare the model presented in this paper to the one presented in [1], using a P-lingua simulator [4]. 2 Modelling the Ecosystem The ecosystem to be modelled is located in the Catalan Pyrenees (NE Spain). This area contains a total of 36 breeding territories of the Bearded Vulture, 65 of the Egyptian Vulture and 525 of the Eurasian Griffon Vulture. In addition to the three vultures, the ecosystem to be modelled is also composed of 9 prey species: the Pyrenean Chamois (Rupicapra pyrenaica), the Red Deer (Cervus elaphus), the Fallow Deer (Dama dama), the Roe Deer (Capreolus capreolus), sheep (Ovis aries), the cow (Bos taurus), the horse (Equus caballus), the goat (Capra hircus) and the wild boar (Sus scrofa). Prey species remains constitutes the basic feeding source for the vultures in the area under study. The three vultures are cliff-nesting and long-lived species characterized by their low fecundity [3]. Concerning their diet, the Bearded Vulture is the only vertebrate that feeds almost exclusively on bone remains of medium size ungulates (see reviews in [6], [5]), whereas the Egyptian vulture feeds on dead small animals and the Eurasian Griffon vultures on medium and large sized animals [3]. P System Based Model of an Ecosystem of the Scavenger Birds 67 The Bearded Vulture has a mind lifespan in wild birds of 21 years [2]. The mean age of first breeding is 8 years. The number of decedents for breeding is one chick. The female’s annual fertility rate in Catalonia in the last years is estimated to be around 38%. The Egyptian Vulture and the Griffon Vulture has a mind lifespan in wild birds of 25 years. The mean age of first breeding is 5 years. The number of descendants per breeding is one chick. The female’s annual fertility rate in Catalonia in the last years is estimated to be around 59% for the Egyptian Vulture and 75% for the Griffon Vulture ([3],[5]). It is accepted that there is the same proportion of females than males in the three types of vultures. The ecosystem modelled in [1] is characterized by the presence of the domestic species, sheep. We considered that species stay all year in the mountain and thus, the bones they left when they die is available for the vultures. The real situation is that there are some domestic animals which live permanently in the mountain whereas others only spend the summer season there. This fact is assumed in the present paper. Taking all this background information into consideration, the following data are required for each species: •I1: age at which adult size is reached. Age at which the animal eats like an adult animal does. Moreover, at this age it will have surpassed the critical early phase during which the mortality rate is high; •I2: age at which it starts to be fertile; •I3: age at which it stops being fertile; •I4: average life expectancy; •I5: fertility ratio (number of descendants by 100 fertile female); •I6: mortality ratio in the first years, age < I1(per cent); •I7: mortality ratio in adult animals, age ≥I1(per cent); •I8: ratio of females in the population (per cent). •I9: amount of bones from young animals when they die (kg) •I10: amount of bones from adult animals when they die (kg) •I11: amount of meet from young animals when they die (kg) •I12: amount of meet from adult animals when they die (kg) •I13: amount of bones necessary per year and animal (kg) •I14: amount of meet necessary per year and adult animal (kg) •I15: amount of grass necessary per year and adult animal (kg) The required information about each species is shown in Table 4 (see Appendix). 68 M. Cardona et al. 3 A formal framework: A P System Based Model of the Ecosystem In this section, we present a model of the ecosystem described in Section 2 by means of probabilistic P systems. We will study the behaviour of this ecosystem under different initial conditions. First, we define the P systems based framework (probabilistic P systems), where additional features such as electrical charges which describe specific properties in a better way, are used. Definition 1. A probabilistic P system of degree qis a tuple Π= (Γ, µ, M1,...,Mq, R, {cr}r∈R) where: •Γis the alphabet (finite and nonempty) of objects (the working alphabet); •µis a membrane structure (a rooted tree), consisting of qmembranes, labelled 1,2,...,q. The skin membrane is labelled by 1. We also associate electrical charges with membranes from the set {0,+,−}, neutral and positive; • M1,...,Mqare strings over Γ, describing the multisets of objects initially placed in the nregions of µ; •Ris a finite set of evolution rules. An evolution rule associated with the membrane labelled by iis of the form r:u[v]α i cr −→ u′[v′]α′ i where u, v, u′, v′are multisets over Γ,α, α′∈ {0,+,−}, and cris a real number between 0 and 1. Besides, for each u, v ∈M(Γ),i∈ {1,2, . . . , q}and α∈ {0,+,−}, it must verify Pt j=1 crj= 1, being r1,...,rtthe rules whose lefthand side is u[v]α i. We denote by [ v→v′]α ithe rule u[v]α i→u′[v′]α′ iin the case u=u′=λ, and α=α′. We assume that a global clock exists, marking the time for the whole system (for all compartments of the system); that is, all membranes and the application of all the rules are synchronized. The multisets of objects present at any moment in the nregions of the system constitutes the configuration of the system at that moment. Particularly, tuple (M1,...,Mq) is the initial configuration of the system. The P system can pass from one configuration to another one by using the rules from Ras follows: •A rule u[v]α i cr −→ u′[v′]α′ iis applicable (with a probability cr) to a membrane labelled by i, and with αas electrical charge, when the multiset uis contained P System Based Model of an Ecosystem of the Scavenger Birds 69 in the father of membrane i, and the multiset vis contained in membrane i. When rule u[v]α i cr −→ u′[v′]α′ iis applied, multiset u(resp. v) in the father of membrane i(resp. membrane i) is removed of that membrane and multiset u′ (resp. v’) is produced in that membrane. •The rules are applied in a maximal consistent parallelism, that is, all those rules of type u1[v1]α i→u′ 1[v′ 1]α′ iand u2[v2]α i→u′ 2[v′ 2]α′ imight be applied simultaneously in a maximal way. •The constants crassociated with the rules indicate the affinity of the above mentioned rule for its application. 3.1 The model The model proposed consists in the following probabilistic P system of degree 2 with two electrical charges (neutral and positive): Π= (Γ, µ, M1,M2, R, {cr}r∈R) where: •Γ={Xij, Yij, Vij, Zij : 1 ≤i≤n, 0≤j≤gi,7} ∪ {b0i, bi: 1 ≤i≤n} ∪ {B, G, M, B′, G′, M′, C, C′} ∪ {Hi, H′ i, Fi, F ′ i, Ti, di, ai: 1 ≤i≤n} is the working alphabet. In our model, n= 17 represents the different types of animals (according to the management) of the 12 species which compose the ecosystem under study. Symbols X,Y,Vand Zrepresent the same animal but in different states. Index iis associated with the species and index jis associated with their age. It also contains the auxiliary symbols B, B′, which represent 0.5 kg of bones, M, M′, which represent 0.5 kg of meet and G, G′, which represent 0.5 kg of grass. Objects Hi, H′ irepresent 0.5 kg of biomass of bones, and objects Fi, F ′ irepresent 0.5 kg of biomass meet left by specie iin different states. Tiis an object that is used for counting the existing animals of species i. If a species overcomes the maximum density, values will be regulated. At the moment when a regulation takes place, object aiallows us to eliminate the number of animals of species ithat exceed the maximum density. Object di is used to put under control domestic animals that are withdrawn from the ecosystem for their marketing. •µ= [ [ ]2]1is the membrane structure. We represent two regions, the skin and an inner membrane. The first is important to check the densities of every species do not overcome the threshold of the ecosystem. Animals reproduce, feed and die in the inner membrane. For the sake of simplicity, neutral polarization will be omitted. • M1and M2are strings over Γ, describing the multisets of objects initially placed in the regions of µ(encoding the initial population and the initial food); 70 M. Cardona et al. –M1={b0i, Xqij ij : 1 ≤i≤n, 0≤j≤gi,7}, where the multiplicity qij indicates the number of animals of species iwhose age is jthat are initially present in the ecosystem; –M2={C}, •The set Rof evolution rules consists of: r0≡[C→G′βC′]0 2. r1≡[b0,i →bi]0 1. – Reproduction-rules. ·Adult males: r2≡[Xij (1−ki,1)·(1−ki,4) −−−→ Yij]0 1,1≤i≤n, gi,5≤j≤gi,7. ·Adult females that reproduce: r3≡[Xij ki,2·ki,1·(1−ki,4) −−−→ YijYki,3 i0]0 1,1≤i≤n, i 6= 5, gi,5≤j < gi,6. r4≡[X5j 0.5·k5,1 −−−→ Y5jYki,3 50 ]0 1, g5,5≤j < g5,6. r5≡[X5j 0.5·k5,1 −−−→ Y5jYki,3 60 ]0 1, g5,5≤j < g5,6. ·Adult females that do not reproduce: r6≡[Xij (1−ki,2)·ki,1·(1−ki,4) −−−→ Yij]0 1,1≤i≤n, gi,5≤j < gi,6. r7≡[Xij ki,1·(1−ki,4) −−−→ Yij]0 1,1≤i≤n, gi,6≤j≤gi,7. ·Young animals that do not reproduce: r8≡[Xij 1−ki,4 −−−→ Yij]0 1,1≤i≤n, 1≤j < gi,5. – Growth rules. r9≡[Xij ki,5·ki,4 −−−→ Yi(gi,5−1)Yij ]0 1,1≤i≤n, gi,5≤j≤gi,7. r10 ≡[Xij (1−ki,5)·ki,4 −−−→ Yij]0 1,1≤i≤n, gi,5≤j≤gi,7. – Mortality rules. r11 ≡bi[ ]0 2→[biagi,8 i]+ 2: 1 ≤i≤n. ·Young animals that survive: r12 ≡Yij[ ]0 2 1−mi,1−mi,3 −−−→ [VijTi]+ 2: 1 ≤i≤n, 0≤j < gi,4. ·Young animals that die: r13 ≡Yij[ ]0 2 mi,1 −−−→[H′fi,1·gi,3 iF′fi,2·gi,3 iB′fi,1·gi,3M′fi,2·gi,3]+ 2: 1 ≤i≤ n, 0≤j < gi,4. P System Based Model of an Ecosystem of the Scavenger Birds 71 ·Young animals that are retired from the ecosystem: r14 ≡[Yij mi,3 −−−→ λ]0 1: 1 ≤i≤n, 0≤j < gi,4. ·Adult animals that do not reach an average life expectancy and survive: r15 ≡Yij[ ]0 2 1−mi,2 −−−→[VijTi]+ 2: 1 ≤i≤n, gi,4≤j < gi,7. ·Adult animals that do not reach an average life expectancy and die: r16 ≡Yij[ ]0 2 mi,2 −−−→[H′fi,3·gi,3 iF′fi,4·gi,3 iB′fi,3·gi,3M′fi,4·gi,3Vki,4 i,gi,5−1Tki,4 i]+ 2: 1≤i≤n, gi,4≤j < gi,7. ·Animals that reach an average life expectancy and die in the ecosystem: r17 ≡Yigi,7[ ]0 2 c17 −−−→[H′fi,3·gi,3 iF′fi,4·gi,3 iB′fi,3·gi,3M′fi,4·gi,3Vki,4 i,gi,5−1Tki,4 i]+ 2: 1≤i≤n, being c17 =ki,4+ (1 −ki,4)·(mi,4+ (1 −mi,4)·mi,2). ·Animals that reach an average life expectancy and retire from the ecosystem: r18 ≡[Yigi,7 (1−ki,4)·(1−mi,4)·(1−mi,2) −−−→ λ]1: 1 ≤i≤n. – Regulation rules. r19 ≡[G′→G]+ 2. r20 ≡[B′→B]+ 2. r21 ≡[M′→M]+ 2. r22 ≡[C′→C]+ 2. r23 ≡[H′ i→Hi]+ 2: 1 ≤i≤n. r24 ≡[F′ i→Fi]+ 2: 1 ≤i≤n. – Evaluation of the density of the different species in the ecosystem r25 ≡[Tgi,8 iagi,8−gi,9 i→λ]+ 2: 1 ≤i≤n. r26 ≡[Vij →Zij]+ 2: 1 ≤i≤n, 0≤j < gi,7. – Feeding rules. r27 ≡[ZijaiBfi,5·gi,3Gfi,6·gi,3Mfi,7·gi,3]+ 2→Xi(j+1)[ ]0 2: 1 ≤i≤n, 0≤ j≤gi,7. – Balance rules. The purpose of these rules is to make a balance at the end of the year. That is, the leftover food is not useful for the next year, so it is necessary to eliminate it. But if the amount of food not is enough, some animals die. ·Elimination of the remaining bones, meet and grass: r28 ≡[B→λ]0 2. 72 M. Cardona et al. r29 ≡[G→λ]0 2. r30 ≡[M→λ]0 2. r31 ≡[Ti→λ]0 2: 1 ≤i≤n. r32 ≡[ai→λ]0 2: 1 ≤i≤n. r33 ≡[bi]0 2→bi[ ]0 2: 1 ≤i≤n. r34 ≡[Hi]0 2→Hi[ ]0 2: 1 ≤i≤n. r35 ≡[Fi]0 2→Fi[ ]0 2: 1 ≤i≤n. ·Young animals mortality: r36 ≡[Zij gi,1 −−−→ H′fi,1 iF′fi,2 iB′fi,1M′fi,2]0 2: 1 ≤i≤n, 0≤j < gi,4. r37 ≡[Zij]0 2 1−gi,1 −−−→ di[ ]0 2: 1 ≤i≤n, 0≤j < gi,4. ·Adult animals mortality: r38 ≡[Zij gi,1 −−−→ H′fi,3 iF′fi,4 iB′fi,3M′fi,4]0 2: 1 ≤i≤n, gi,4≤j≤gi,7. r39 ≡[Zij 1−gi,1 −−−→ λ]0 2: 1 ≤i≤n, gi,4≤j≤gi,7. r40 ≡[Hi→λ]0 1: 1 ≤i≤n. r41 ≡[Fi→λ]0 1: 1 ≤i≤n. The constants associated with the rules have the following meaning: •gi,1: 1 for wild animals and 0 for domestic animals. •gi,2: 1 for carnivorous animals and 0 otherwise. •gi,3: proportion of time that they remain in the mountain during the year. •gi,4: age at which adult size is reached. This is the age at which the animal eats like and adult does, and at which if the animal dies, the amount of biomass it leaves is similar to the total one left by an adult. Moreover, at this age it will have surpassed the critical early phase during which the mortality rate is high. •gi,5: age at which it starts to be fertile. •gi,6: age at which it stops being fertile. •gi,7: average life expectancy in the ecosystem. •gi,8: maximum density of the ecosystem. •gi,9: number of animals that survive after reaching maximum density of the ecosystem. •ki,1: proportion of females in the population (per one). •ki,2: fertility ratio (proportion of fertile female that reproduce). •ki,3: number of descendants per each fertile female that reproduce. P System Based Model of an Ecosystem of the Scavenger Birds 73 •ki,4: it is equal to 0 when the species go through a natural growth (animals which remain in the same territory throughout their lives) and it is equal to 1 when animals are nomadic (the Bearded Vulture moves from one place to another until it is 6–7 years old, when it settles down). •ki,5: population growth (per one). •mi,1: natural mortality ratio in first years, age < gi,4(per one). •mi,2: mortality ratio in adult animals, age ≥gi,4(per one). •mi,3: percentage of domestic animals withdrawn in the first ages of the not stabilized populations. •mi,4: is equal to 1 if the animal dies at the age of gi,7and it is not retired, and it is equal to 0 if the animal not dies at the age of gi,7but it is retired from the ecosystem. •fi,1: amount of bones from young animals when they die, age < gi,4. •fi,2: amount of meet from young animals when they die, age < gi,4. •fi,3: amount of bones from adult animals when they die, age ≥gi,4. •fi,4: amount of meet from adult animals when they die, age ≥gi,4. •fi,5: amount of bones necessary per year and animal (1 unit is equal 0.5 kg of bones). •fi,6: amount of grass necessary per year and animal. •fi,7: amount of meet necessary per year and animal. The constants used in this work are the same than those of [1], except for those referring to the maximum density of the population, the meet or the grass. However, they have been renamed in this work in order to be able to group them according to their characteristics. Thus, general characteristics are now named with g, those of reproduction with k, those corresponding to mortality with mand those of feeding with f. See Appendix in table 5. 3.2 Structure of the P system running The model presented in [1], shows some restrictions which produce undesired effects for the study of the ecosystem evolution. Thus, in the first version of the model, it was not born in mind the resources for the feeding of herbivorous species, that is, it was assumed that there was enough grass at the ecosystem for all the population. Similarly, the maximum density of certain species in some areas of the ecosystem was not taken into consideration. It has been experimentally proved that, when the number of animals of a species exceeds a threshold, a phenomenon of autoregulation of the population takes place. In this paper, we present a new model of the ecosystem that includes new ingredients with the aim to overcome the limitations previously described. More specifically, the modifications made are the following: 74 M. Cardona et al. •It has been added new species which have active roles in the ecosystem under study, although their roles are perhaps less relevant that those of the first species studied. These species are the wild boar, the horse, the goat and the cow. Besides, it has been included greedy species such as the Egyptian Vulture and the Griffon Vulture which compete with the Bearded Vulture. •A new module has been added in order to regulate the population density of the ecosystem. •The mortality module has been modified in order to consider that after an animal dies, in addition to the bones it leaves at the ecosystem, its meet serves as food for other animals. •The feeding module has also been modified because the feeding resources for the species at the ecosystem have been modelled in this new approach. For this reason, new objects have been introduced representing, apart from the bones, the amount of meet and grass available at the ecosystem. In the model presented in Section 3.1, a new module devoted to control the density has been introduced. From the point of view of the execution of the system, the new module has been incorporated between the Mortality and the Feeding modules. These are depicted in Figure 1. Fig. 1. Modules of the P systems Let us recall that in the model presented in [1], objects Xrepresent the different species along the execution of the reproduction module. Objects Xevolve to objects Ywhen they pass to the mortality module, and these objects Yevolve to objects Zwhen they pass to the feeding module. Finally, the cycle is completed when objects Zevolve to objects X. In order to keep the representation of the species at the different modules, we have used objects Vto describe the species at the density module. For that purpose, objects Y(mortality module) evolve to objects V(density module), together with objects Twhich represent the number of individuals per each species. Then, objects Vevolve to objects Z(feeding module). By the way, objects Twill allow P System Based Model of an Ecosystem of the Scavenger Birds 75 the activation of the process of auto–regulation of the ecosystem when the number of individuals of a species exceed the threshold of maximum density, which is codified by objects a. When a cycle is produced, all objects which are not associated with species are eliminated, except the biomass generated by the animals that have died due to the process of regulation. 4 Results and discussions The software tool used for the purposes of this paper is based on P-Lingua 2.0 [4], P-Lingua is a new programming language able to define P systems of different types (from now on, frameworks). For instance, P-Lingua can define any P system within the probabilistic framework mentioned in this paper. Next, we describe how to implement in P–Lingua the applicability of the rules to a given configuration. (a) Rules are classified into sets so that all the rules belonging to the same set have the same left–hand side. (b) Let {r1,...,rt}be one of the said sets of rules. Let us suppose that the common left-hand side is u[v]α iand their respective probabilistic constants are cr1,...,crt. In order to determine how these rules are applied to a give configuration, we proceed as follows: – It is computed the greatest number N so that uNappears in the father membrane of iand vNappears in membrane i. – N random numbers xsuch that 0 ≤x < 1 are generated. – For each k(1 ≤k≤t) let nkbe the amount of numbers generated belonging to interval [ Pk−1 j=0 crj,Pk j=0 crj) (assuming that cr0= 0). – For each k(1 ≤k≤t), rule rkis applied nktimes. P-Lingua 2.0 provides a JAVA library that defines algorithms in order to simulate P system computations for each supported framework, so we are using a common algorithm for all P systems within the probabilistic framework. By defining the ecosystem model by a P system written in P-Lingua, it is possible to check, validate and improve the model in a flexible way, instead of developing a new “ad hoc” simulator for each new model. The application has a friendly user-interface, which sits on the P-Lingua JAVA library, allowing the user to change the initial parameters of the ecosystem in an easy way without special knowledge about the P system or the initial multisets. The main objective is to make virtual experiments over the ecosystem. The current version of this software is a prototype GPL licensed [8]. In order to compare the model presented in this work to the one presented in [1], it has been used the P-lingua simulator [4]. We have simulated the evolution of the 82 M. Cardona et al. matrix associated with the chain), and (b) for any initial distribution, µ(0) and for any stationary distribution πfor the Markov chain, the sequence (µ(n))n∈Nconverges to πin total variation as n→ ∞ (that is, the Markov chain is approaching equilibrium as n→ ∞). In the paper [2], a classification of states of a finite and homogeneous Markov chain is provided by using P systems. Moreover, the period was calculated for recurrent classes. The design of the P systems was inspired in properties used in classic algorithms that deal with the problem of the classification. Especially, this solution allows us to decide whether an irreducible Markov chain is aperiodic or not. The main goal of this paper is to design a P system associated with an irreducible Markov chain which provides an answer to the aperiodicity of the chain. If the answer is negative, then the system provides the period of the chain. The solution presented is based on a characterization of the aperiodicity in existential terms of some state and a natural number, and it is semi–uniform, in the sense that for each Markov chain, a P system associated with it is constructed. Besides, the solution spends a polynomial amount of resources in the sense of the computational complexity theory in Membrane Computing. The solution presented in the paper improves the solution obtained in [2], because less computational resources are used. The paper is organized as follows. In the following section, we recall some basic notions and results that we use in the paper. In Section 3, a P system associated with an irreducible Markov chain is designed in order to study the periodicity of that class. Section 4 shows a formal verification of the designed P system. In Section 5, the solution presented is compared with another solution obtained from [2]. Finally some conclusions are presented. 2 Preliminaries A discrete Markov chain is a sequence {Xt|t∈N}of random variables whose values are called states, that verifies the following property: P(Xt+1 =j/X0=i0, X1=i1,...,Xt=it) = P(Xt+1 =j/Xt=it) Without loss of generality, we can suppose that the state space is the set of nonnegative integers. The value of variable Xtis interpreted as the state of the process at instant t. In this paper we work with Markov chains having a finite state space S={s1,...,sk}. A discrete Markov chain is characterized by the transition probability pij(t) = P(Xt=sj/Xt−1=si),∀t≥1 where pij(t) provides the transition from state sito state sjat time t−1. The matrix of transition probabilities Characterizing the Aperiodicity of Irreducible Markov Chains 83 P(t) = (pij(t))1≤i,j≤k is a stochastic matrix, that is, is nonnegative for all tand the sum of each arrow is equal to 1, Pk j=1 pij(t) = 1. We say that the chain is time homogeneous or stationary if pij(t) = pij for each tand it verifies the Kolmogorov-Chapman equation: p(1) ij =pij, p(2) ij = k X l=1 pilplj, . . . , p(n) ij = k X l=1 pilp(n−1) lj , where p(n) ij is the transition probability of state sito state sjat time n. We denote the initial distribution by means of the vector µ(0) = (µ(0) 1,...,µ(0) k) = (P(X0=s1), P(X0=s2),...,P(X0=sk)) and the distribution of the Markov chain at time nis µ(n)= (µ(n) 1,...,µ(n) k) = (P(Xn=s1), P(Xn=s2),...,P(Xn=sk)) Then, µ(n)=µ(0) ·P(n), where P= (pij) is the transition matrix of the homogeneous Markov chain. Next, we introduce some concepts and results related to the states of a homogeneous Markov chain. We say that a state sjcommunicates with another state si(and we denote it by si→sj), if there exists a natural number n > 0 such that p(n) ij >0 (that is, if the chain has a positive probability of ever reaching sjwhen we start from si. We say that the states siand sjintercommunicate (and we denote it by si↔sj) if si→sjand sj→si. In the finite state space S={s1,...,sk}of a Markov chain, the relation ↔ is an equivalence relation and we can consider the corresponding quotient set {s1,...,sk}/↔whose elements are the classes of equivalence by ↔. A Markov chain with state space S={s1,...,sk}is said to be irreducible if there exists only one class of equivalence by ↔; that is, if for all si, sj∈Ewe have si↔sj. Otherwise, the chain is said to be reducible. We say that a state siis recurrent or essential if for each natural number m and for each state sjverifying p(m) ij >0 there exists a natural number nsuch that p(n) ji >0. Otherwise, the state is said to be transient. A recurrent class is the equivalence class determined by a recurrent state. It is easy to prove that from a recurrent state, only recurrent states belonging to the same class are reachable. Arecurrence time of siis a natural number n > 0 such that p(n) ii >0. The period of a state siis defined as d(i) = g.c.d. {n≥1|p(n) ii >0}, that is, it is the greatest common divisor of the recurrence times associated with it. All states belonging to the same class have the same period. Then, we can define the period of a class of a given Markov chain in a natural manner: it is the period of any state of the class (see [3] and [4] for more details). 84 M. Cardona et al. Definition 1. A Markov chain is said to be aperiodic if all its states are aperiodic; that is, their periods are equal to 1. Otherwise, the chain is said to be periodic. Next, we provide a method to compute the period of a recurrent class and a characterization of the periodicity of a class. Theorem 1. Let A={s1,...,sr}be a recurrent class. The period of Ais d=g.c.d. {n|p(n) ii >0; 1 ≤i, n ≤r}. That is, the period of Ais the greatest common divisor of all times of recurrences of the states of that class, smaller than or equal to r. Proof. By definition, given a state si(1 ≤i≤r) its period is d(i) = g.c.d. {n≥1|p(n) ii >0}. As all states have the same period d, we have d=d(1) = d(2) = ...=d(r) = g.c.d. {n≥1|p(n) ii >0; 1 ≤i≤r}. Let d′=g.c.d.{n|p(n) ii >0; 1 ≤i, n ≤r}. Let us see that d=d′. For that, we will check that any trajectory from a state si∈Ato itself, with the length bigger than r, is the composition of trajectories with length smaller than or equal to r between the same states. Let n > r be a time of recurrence associated with a state si∈A, that is, p(n) ii >0. There exists a state si0such that p(n) ii ≥p(n′) ii0·p(n0) i0i0·p(n′′ ) i0i>0, being n=n′+n0+n′′. Thus, n0and n′+n′′ are also times of recurrence. If n0> r or n′+n′′ > r, then we repeat the process until we obtain a decomposition p(n) ii ≥p(n′) ii0·p(n0) i0i0·p(n1) i1i1. . . p(nr) irir·p(n′′ ) iri>0 with 1 ≤i1,...,ir≤r,n=n′+n1+...+nr+n′′ verifying n′+n′′ ≤rand n1,...,nr≤r. Finally, let us notice that substituting p(n) ii , with n > k, by a suitable sequence of p(m) ii , with m≤k, the g.c.d. is the same. ¤ Lemma 1. Let A={a1,··· , ar}be a set of natural numbers. Let us suppose g.c.d. {a1,··· , ar}= 1. Let us denote by A+the set of all positive linear combinations λ1a1+··· , λrar, with λi∈Z+,1≤i≤r. Then, there exists a natural number Nsuch that n∈A+for all n≥N. Proof. See, e.g., the appendix of [1] ¤ Next, we characterize the aperiodicity of a recurrent class of a finite Markov chain through the existence of a state sjreachable from each state si. Characterizing the Aperiodicity of Irreducible Markov Chains 85 Theorem 2. Let {Xt|t∈N}be a Markov chain with state space S={s1,...,sk} and transition matrix P= (pij). (1) If {Xt|t∈N}is aperiodic, then there exists a natural number Nsuch that p(n) ii >0, for all i(1 ≤i≤k)and all n≥N. (2) If {Xt|t∈N}is irreducible and aperiodic, then there exists a natural number Msuch that p(n) ij >0, for all i, j (1 ≤i, j ≤k)and all n≥M. Proof. See, e.g., Chapter 4 from [3] ¤ Theorem 3. Let A={s1, . . . , sr}be a recurrent class of a finite Markov chain. The following are equivalent: (1) Class Ais aperiodic. (2) There exists a state sj∈Aand a natural number m0∈Nsuch that p(m0) ij >0 for all state si∈A. Proof. Let us suppose that class Ais aperiodic. Then all states in Ahave the same period d= 1. From Theorem 2 there exists a natural number Nsuch that p(n) ii >0, for all i(1 ≤i≤r) and all n≥N. Given j(1 ≤j≤r), we define ni(j) = min{n|p(n) ij >0}, for each si∈A,n(j) = max{n1(j), . . . , nr(j)}, and m0=N+n(j). Let us see that p(m0) ij >0, for each i(1 ≤i≤r). We have p(m0) ij ≥p(ni(j)) ij p(m0−ni(j)) jj >0 because of p(ni(j)) ij >0 by definition of ni(j), and p(m0−ni(j)) jj >0 by Theorem 2. Conversely, let us suppose that there exists m0≥1 and a state sj∈Asuch that ∀si∈Awe have p(m0) ij >0. In particular, p(m0) jj >0 so m0is a recurrence time. On the one hand, if dis the period of the class, then m0is a multiple of d. On the other hand, if si∈Ais a state such that pji >0, then 0 < p(m0) ij pji ≤p(m0+1) ii , so m0+ 1 is a multiple of d. Hence, d= 1. ¤ 3 A P System Associated with an Irreducible Markov Chain The goal of this paper is to study the aperiodicity of an irreducible Markov chain with state space S={s1,...,sk},k≥2, by using P systems. In the affirmative case, the answer of the system is Y ES, on the contrary, the system sends an object encoding the period of the class to the environment. 3.1 The Design of the P System Let Pk= (pij)1≤i,j≤kbe a Boolean matrix associated with a class with a finite and homogeneous Markov chain of order ksuch that pij = 1 if the transition from sito sjis possible, and pij = 0 otherwise; that is, Pkis the adjacency matrix of the directed graph associated with the recurrent class. 86 M. Cardona et al. The solution presented in this paper is a semi–uniform one in the following sense: we give a family Π={Π(Pk)|k∈N}, associating with Pka P system with external output, such that: •There exists a deterministic Turing machine working in polynomial time which constructs the system Π(Pk) from Pk. •The output of the P system Π(Pk) provides the classification of the recurrent class of the Markov chain as well as the period of the states. We associate with the matrix Pkthe P system of degree 4 with external output, Π(Pk) = (Γ(Pk), µ(Pk),M1,M2,M3,M4, R) defined as follows: •Working alphabet: Γ(Pk) = {sij , tij , τij |1≤i, j ≤k} ∪ {sijr |1≤i, j, r ≤k} ∪ {Tr|0≤r≤k} ∪ {βl|0≤l≤k−1} ∪ {bi|1≤i≤k} ∪ {pr|1≤r≤k} ∪ {ci, di|0≤i≤α} ∪ {yes, Y ES, σ, } where α= 3k+⌈k 2⌉. In the working alphabet the objects: –sii represents (at the initial configuration) the state siof the chain. –tij and τij represent the elements pij of the Boolean matrix associated with the transition matrix of the Markov chain. –sijr represents the existence of a path of length rfrom the state sito state sj. –Trand prrepresent the existence of a recurrence time equal to rin different configurations. –τij represents that the state sjis reachable from state si. •Membrane structure: µ(Pk) = [ [ [ [ ]1]2]3]4. •Initial multisets: M1={tpij ij |1≤i, j ≤k} ∪ {β0} M2={sii |1≤i≤k} M3={bi|1≤i≤k} ∪ {d0} M4=∅ •The set Rof evolution rules consists of the following rules: r1(ij)≡[tij →τijtk ij]1,1≤i, j ≤k r2(i)≡[βi→βi+1]1,0≤i≤k−2 r3≡[βk−1]1→ck 0 r4(rij)≡[crsij τpj1 j1. . . τpjk jk ]2→[spj1 i1. . . spjk ik cγj r+1]2spj1 i1r+1 . . . spjk ikr+1Tpji r+1, 1≤i, j ≤k, 0≤r≤α−1, γj=Pk l=1 pjl Characterizing the Aperiodicity of Irreducible Markov Chains 87 r5≡[σ]2→σ r6(jr)≡[s1jr . . . skjr]3→[σ]2yes, 1≤j≤k, 1≤r≤α r7(r)≡[Trbr→pr]3,1≤r≤k r8(il)≡[pipi+l→pipl]3,1≤i≤k, 1≤l≤k−i r9(i)≡[p2 i→pi]3,1≤i≤k r10(i)≡[di→di+1]3,0≤i≤α−1 r11(r)≡[dαpr]3→pr[ ]3,2≤r≤k r12 ≡[dαp1]3→yes[ ]3 r13 ≡[yes]4→Y ES[ ]4 r14(r)≡[pr]4→pr[ ]4,1≤r≤k 3.2 An Overview of Computations Initially, membrane 1 contains objects tij that codify the elements pij of the Boolean matrix associated with the transition matrix of the Markov chain, together with the counter β0. This counter allows us to dissolve membrane 1 at a certain instant. Membrane 2 contains initially objects sii that codify the states si of the chain. Membrane 3 contains objects bithat will be used in order to avoid that repeated recurrence times smaller than or equal to kappear. The counter d in membrane 2 will be used to trigger the answer at the suitable instant. The design of the P system Π(Pk) implements a process that is structured by stages. The first one consists of ksteps which allow the production of sufficiently many new copies τij of objects tij . This is done by applying rules of type r1and r2in membrane 1 at k−1 first steps and applying at step krule r3that dissolves membrane 1. At the second stage, all paths between states with length at most k, as well as recurrence times smaller than or equal to k, are generated. This stage starts at step k+ 1 and it spends at most ksteps. First, rules of type r4are applied producing objects sijr in membrane 3 that codify the existence of a path with length rfrom state sito state sj, as well as the objects Trcodifying the existence of a recurrence time equal to r. Simultaneously, it is checked if there exists a state sjand a natural number m0such that p(m0) ij >0, for all states si. In that case, an object σis produced in membrane 2 and the system expels an object Y ES to the environment. The third stage is only applied if an object Y ES has not been expelled to the environment. At this stage, the period of the class is computed and it takes k+⌈k 2⌉steps. By applying rules of type r7, objects prencoding recurrence times smaller than or equal to k, are obtained. Such recurrence times are different from each other. By applying rules of types r8and r9, the greatest common divisor of 88 M. Cardona et al. these times is computed. If the period of the class is equal to 1, then the system sends an object Y ES to the environment, otherwise, the system expels an object pnthat encodes the period of the class to the environment. 4 Formal Verification Given a computation Cof the P system Π(Pk), for each m∈Nwe denote by Cmthe configuration of the system obtained after the execution of msteps. For each label l∈ {1,2,3}, we denote by Cm(l) the multiset of objects contained in membrane lin the configuration Cm. Besides, we denote by Cm(env) the content of the environment of the system in the configuration Cm. Proposition 1. (First stage) We have the following: (1) For each m,1≤m≤k−1, we denote ψm= 1 + k+k2+... +km= (km+1 −1)/(k−1). Then Cm(1) = {βmtkm·pij ij τψm−1·pij ij }. (2) Ck(2) = {ck 0, sii, τψk−1·pij ij , t(kk)·pij ij |1≤i, j ≤k} Proof. (1) By induction on m. Let us see the result for m= 1. First, we notice that rule r2(0) is applicable to configuration C0, so β1∈ C1(1). Rule r1(ij) is applicable to configuration C0if and only if pij = 1. Hence, C1(1) = {β1tk·pij ij τpij ij }. Let mbe such that 1 ≤m < k −1 and Cm(1) = {βmtkm·pij ij τψm−1·pij ij }. Then, rule r2(m) is applicable to configuration Cm, so βm+1 ∈ Cm+1(1). Rule r1(ij) is applicable to configuration Cmif and only if pij = 1. Hence, Cm+1(1) = {βm+1 tkm·k·pij ij τ(ψm−1+km)·pij ij }. (2) From (1), we have Ck−1(1) = {βk−1tkk−1·pij ij τψk−2·pij ij }. Next, rule r1(ij) produces kobjects tij and an object τij for each object tij ∈ Ck−1(1). Moreover, rule r3produces kcopies of c0dissolving membrane 1. ¤ Remark: Let us notice that condition τij ∈ Cr(1), 1 ≤r≤k−1, means that state sjis reachable from state si. Lemma 2. For each i, j, r (1 ≤i, j, r ≤k)we have the following: •The sum of the multiplicities of objects s1j. . . skj in Ck+r(2) is, at most, kr. •There exists, at most, kr+1 objects crin Ck+r(2). •τ(ψk−1−ψr−1)·pij ij ∈ Ck+r(2). Characterizing the Aperiodicity of Irreducible Markov Chains 89 Proof. By induction on r. Let us suppose that r= 1, Let i, j be such that 1 ≤i, j ≤k. From (2) in Proposition 1 we have Ck(2) = {ck 0, sii, τψk−1·pij ij } ⊆ Ck(2). Then, rules r4(0,1,1),...,r4(0, k, k) must be applied. If pij = 1, then an object sij (resp. an object τij ) is produced (resp. is consumed) by the application of rule r4(0, i, i) (besides, these objects can only be spent/produced by the application of that rules). Hence, the sum of multiplicities of objects s1j,...,skj will be p1j+...+pkj ≤k, there exists at most k2objects c1in Ck+1(2), and τ(ψk−1−1) ij ∈ Ck+1(2). Let r≥1, r < k, and let us suppose that the result holds for r. Let i, j be such that 1 ≤i, j ≤k. By the induction hypothesis the sum of the multiplicities of objects s1i,...,ski in Ck+r(2) is, at most, kr, there exists, at most, kr+1 objects crin Ck+r(2), and τ(ψk−1−ψr−1)·pij ij ∈ Ck+r(2). For each i(1 ≤i≤k) the rules r4(r1i),...,r4(rki) will be applied to configuration Ck+r(2) at most krtimes, so at most krobjects τij will be spent and kr·kobjects cr+1 will be produced. Then, there exists at most kr+2 objects cr+1 in Ck+r+1(2), and τ(ψk−1−ψr−1−kr)·pij ij ∈ Ck+r+1(2). Moreover, each object siq (1 ≤q≤k) produces, at most, an object sij in Ck+r+1(2). Hence, the sum of multiplicities of s1j,...,skj in Ck+r+1(2) will be, at most, kr+...+kr=k·kr=kr+1.¤ Proposition 2. (Second stage) For each i, j, r (1 ≤i, j, r ≤k)we have: (1) Objects sij and crbelong to Ck+r(2) if and only if there exists a trajectory from state sito state sjwith a length r. (2) A state sof the Markov chain has a recurrence time rif and only if Tr∈ Ck+r(3). Proof. (1) By induction on r. Let us suppose that r= 1. If sij, c1∈ Ck+1(2), then rule r4(0, i, i) must be applied by using objects c0, sii, τij ∈ Ck(2). Then, pij = 1, otherwise pij = 0 ⇒ τij /∈ Ck(2) (from Proposition 1). Let i0, j0(1 ≤i0, j0≤k) and let us suppose that there exists a trajectory from state si0to state sj0with a length 1. Then, pi0j0= 1. From Proposition 1 we deduce that Ck(2) = {ck 0, sii, τψk−1·pij ij , t(kk)·pij ij |1≤i, j ≤k}, so for each i(1 ≤i≤k) rule r4(0ii) is applied once to configuration Ck(2). Then, {c1, si0j0} ⊆ Ck+1(2). Let r≥1, r < k, and let us suppose that the result holds for r. Let i, j (1 ≤ i, j ≤k) be such that sij, cr+1 ∈ Ck+r+1(2). On the one hand, rule r4(ril) has been applied, at least once, to configuration Ck+rby using objects cr, sil, τlj (for some l, 1 ≤l≤k). So, plj = 1. On the other hand, cr, sil ∈ Ck+r(2). Then, by induction hypothesis we deduce that there exists a trajectory with a length rfrom state sito state sl. Hence, there exists a trajectory with the length r+ 1 from state sito state sj. 90 M. Cardona et al. Let i0, j0(1 ≤i0, j0≤k) and let us suppose that there exists a trajectory from state si0to state sj0with a length r+ 1. Then, there exists a trajectory from state si0to state sn0with a length r(for some n0, 1 ≤n0≤k) such that pn0j0= 1. From the induction hypothesis we have si0n0, cr∈ Ck+r(2), and from Lemma 2 we deduce that {τ(ψk−1−ψr−1)·pn0j n0j|1≤j≤k} ⊆ Ck+r(2) Then, by applying rule r4(r, i0, n0) once, we obtain {cr+1, spn0j i0j: 1 ≤j≤ k} ⊆ Ck+r+1(2). Hence, si0j0∈ Ck+r+1(2) because of pn0j0= 1. (2) Let r(1 ≤r≤k) be the recurrence time of a state si. From (1), we deduce that sii, cr∈ Ck+r(2). Therefore, rule r4(rij) has been applied to configuration Ck+r−1, for some j, 1 ≤j≤k, such that pji = 1, and some object cr−1∈ Ck+r−1(2). Then, Tpji r=Tr∈ Ck+r(3). Let r(1 ≤r≤k) such that Tr∈ Ck+r(3). Then rule r4(r−1, i, j) has been applied to configuration Ck+r−1, for some objects sij, cr−1such that pji = 1. From (1) there exists a trajectory with a length r−1 from state sito state sj. Hence, there exists a trajectory with a length rfrom state sito state si.¤ Theorem 4. (Output of the system) Let Sbe an irreducible homogeneous Markov chain of order k. Let α= 3k+⌈k 2⌉. We have the following: (1) The class Sis aperiodic if and only if there exists r(1 ≤r≤α−k)such that configuration Ck+r+2 of Π(Pk)is a halting configuration and Ck+r+2(env) = {Y ES}. (2) The class Sis periodic with period equal to n > 1if and only if configuration Cα+2 of Π(Pk)is a halting configuration and Cα+2(env) = {pn}. Proof. Let Sbe an irreducible homogeneous Markov chain. (1) Let us suppose that Sis aperiodic. From Theorem 3, there exists a state sj0 and a natural number q > 0 such that ∀i(1 ≤i≤k⇒p(q) ij0>0). Then, for each i, 1≤i≤k, there exists a trajectory with a length qfrom state sito state sj0. - If q≤k, from (1) Proposition 2 we deduce that s1j0,...,skj0, cq∈ Ck+q(2). These objects have been produced by the application of rules r4(q−1,1, j1),...,r4(q−1, k, jk) to configuration Ck+q−1, for some j1,...,jk such that pj1,j0=···=pjk,j0= 1. So, s1j0q,...,skj0q∈ Ck+q(3). So, by applying the rule r6(j0, q) to configuration Ck+q, we have {yes} ∈ Ck+q+1(4) and σ∈ Ck+q+1(2). At the next step, rules r5and r13 are applied. Then, Ck+q+2(env) = {Y ES}, membrane 2 is dissolved and the system halts. - If q > k, then any rule of the type r6is not applicable. From Proposition 2 we have encoded the recurrence times (smaller than or equal to k) in membrane 3 by objects T. Then, some rule of the type r7produces objects pcorresponding to objects T. Next, by applying suitable rules r8and r9 Characterizing the Aperiodicity of Irreducible Markov Chains 91 we compute the greatest common divisor of these recurrence times (from Theorem 1 we know that g.c.d. is equal to the period of the class). From the aperiodicity of the class S, we deduce that object p1belongs to Cα(3). Then, the rule r12 produces an object yes in Cα+1(4), and we obtain that Cα+2(env) = {Y ES}by applying the rule r13. Then, the system halts. Let us suppose that there exists r(1 ≤r≤α−k) such that configuration Ck+r+2 is a halting configuration and Ck+r+2(env) = {Y ES}. Then, rule r13 has been applied to configuration Ck+r+1(4), and yes ∈ Ck+r+1(4). - If r≤k, then the rule r6(jr) (for some j, 1 ≤j≤k) has been applied to configuration Ck+r, with s1jr,...,skjr ∈ Ck+r(3), and s1j,...,skj , cr∈ Ck+r(2). From (1) in Proposition 2, there exists a trajectory with a length rfrom state sito state sj, for each i(1 ≤i≤k). From Theorem 3 we conclude that class Sis aperiodic. - If r > k, object yes has been sent to membrane 4 by applying the rule r12 using objects dαand p1. But object p1has been produced by the iterated application of rules r8and r9. As these rules compute the greatest common divisor of recurrence times, we deduce that the period of Sis equal to 1. (2) Now, let us suppose that the period of Sis n > 1. From Theorem 3 we deduce that for each j, 1≤j≤k, and for each n′>0 there exists i, 1≤i≤k, such that p(n′) ij = 0. From (1) in Proposition 2 we have {sij, cn′}*Ck+n′(2). So, sijn′/∈ Ck+n′(3) and any rule of the type r6is applicable to configuration Ck+n′+1. Next, rules of type r7,r8,r9compute the g.c.d. of the recurrence times. Finally, object pnis sent to the environment after α+2 steps by applying rules r11 and r14. Then, the system halts. Let us suppose that configuration Cα+2 is a halting configuration and Cα+2(env) = {pn}. Then, any rule of the type r6will not be applied, so rules r7, r8, and r9will be applied computing the g.c.d of the recurrence times (smaller than or equal to k) of states si. Hence, class Sis periodic and its period is equal to n.¤ 5 Results and Discussions In [2] a P system was constructed which allows us to classify the states of a Markov chain. Thus, that P system can be adapted to characterize the aperiodicity of such a chain. Specifically, if Pk= (pij )1≤i,j≤kis the Boolean matrix associated with the states of a recurrent class of a finite and homogeneous Markov chain of order k, then we define the system Π′(Pk) = (Γ′(Pk), µ′(Pk),M′1,M′2,M′3,M′4, R′, ρ′) as follows: •Working alphabet: 98 L. Ciencialov´a et al. fixed: it is usually one, two or three. The rules are also of a very simple form. As we will see, they allow the transformation of objects inside the cells and the transportation of objects between the cells and the environment. The rules are grouped into programs. A program contains exactly as many rules, as the number of objects allowed to be present inside the cell. The rules of the programs are applied to the objects inside the associated cells in parallel, and this also affects the objects which are in the environment. The P colony executes a computation by synchronously applying the programs to the objects inside the cells and outside in the environment until a halting configuration is reached. The result of the computation is obtained as the vector of copies of certain “final” objects present in the environment after the system halts. In the following, after providing the formal definitions, we first give a short overview of results on the computational completeness of the different P colony variants. Then we present new results about two types of systems: first about the simplest possible P colonies, those which only have one object inside every cell, and then about a new type called P colonies with senders and consumers, which have special rules for insertion-deletion. We show that both kinds of these very simple devices are able to compute any recursively enumerable set of vectors of non-negative integers. 2 Preliminaries Let Vbe an alphabet, let V∗be the set of all words over V, and let εdenote the empty word. We denote the number of occurrences of a symbol a∈Vin wby |w|a. The set of non-negative integers is denoted by N. A multiset over an arbitrary (not necessarily finite) set Vis a mapping M: V→Nwhich assigns to each object a∈Vits multiplicity M(a) in M. The support of Mis the set supp(M) = {a|M(a)≥1}. If Vis a finite set, then Mis called a finite multiset. A multiset Mis empty if its support is empty, supp(M) = ∅. We will represent a finite multiset Mover Vby a string wover the alphabet Vwith |w|a=M(a), a ∈V, and εwill represent the empty multiset. We will also need the notion of a register machine which consists of a finite number of registers each of which can hold an arbitrarily large non-negative integer (we say that the register is empty if it holds zero), and a set of labeled instructions which specify how the numbers stored in the registers can be changed. Formally, a register machine is a construct M= (m, H, l0, lh, R), where mis the number of registers, His the set of instruction labels, l0is the start label, lh is the halting label, and Ris the set of instructions. Each label from Hlabels only one instruction from R. There are several types of instructions which can be used. For li, lj, lk∈Hand r∈ {1, . . . , m}we have •li: (ADD(r), lj, lk) - nondeterministic add: Add one to register rand then go to one of the instructions with labels ljor lk, non-deterministically chosen. On Very Simple P Colonies 99 •li: (SUB(r), lj, lk) - subtract: If register ris non-empty, then subtract one from it and go to the instruction with label lj, if the value of register ris zero, go to instruction lk. •lh:HALT -halt: Stop the machine. A register machine Mcomputes a set N(M) of numbers in the following way: It starts with empty registers by executing the instruction with label l0and proceeds by applying instructions as indicated by the labels (and made possible by the contents of the registers). If the halt instruction is reached, then the number stored at that time in register 1 is said to be computed by M. Because of the nondeterminism in choosing the continuation of the computation in the case of ADD instructions, N(M) can be an infinite set. It is known (see, e.g., [6]) that in this way we can compute all sets of numbers which are Turing computable. If a set of output registers i1, . . . , ir,1≤r≤m, ij∈ {1, . . . , m}is specified, then Mcomputes a set of vectors of non-negative integers as follows. If the halt instruction is reached, then (v1, . . . , vr), where vkis the number stored in register ik, 1 ≤k≤r, is the vector of numbers computed by M, i.e., the result of that computation. Now we recall the definition of a P colony from [5]. A P colony is a construct Π= (V, e, F, C1, . . . , Cn), n ≥1,where Vis an alphabet (its elements are called objects). There are two kinds of distinguished objects: e∈V(the environmental object), and the objects in F⊆V(the set final objects). The cells of the colony are denoted by C1, . . . , Cn. Each cell is a pair Ci= (Oi, Pi), where Oiis a multiset over {e}having the same cardinality called capacity (here we only consider |Oi| ∈ {1,2}) for all i, 1≤i≤n(the initial state of the cell), and Piis a finite set of programs. Each program consists of rules of the following forms: •a→b(internal point mutation), specifying that an object a∈Vinside the cell is changed to b∈V. •c↔d(one object exchange with the environment), specifying that if c∈V is contained inside the cell and d∈Vis present in the environment, then cis sent out of the cell while dis brought inside. •c↔d/c ↔d0(checking rule for one object exchange with the environment), specifying that if c∈Vis inside the cell then it is exchanged with d∈Vfrom the environment, or if there is no doutside but d0∈Vis present, then cis exchanged with d0. •c↔d/c →d0(checking rule for one object exchange with the environment or internal point mutation), specifying that if the exchange of c∈Vinside and d∈Voutside is not possible, then cis changed to d0∈V. The programs contain one rule for each element of Oi, thus, the number of rules of a program coincides with the cardinality of Oi, 1 ≤i≤n. In addition, P colonies with capacity of two may have programs of the form 100 L. Ciencialov´a et al. • ha, in;bc →diwith a, b, c, d ∈V(deletion programs), specifying that if bc is present inside the cell and ais present in the environment, then the objects inside are changed to dand ais brought in. • ha, out;b→cdiwith a, b, c, d ∈V(insertion programs), specifying that if ab is inside the cell, then ais sent out and bis changed to cd. The programs of the cells are used in the non-deterministic maximally parallel manner: in each time unit, each cell which is able to use one of its programs should use one. The use of a program means the application of the rule(s) of the program to the object(s) in the cell. This way, transitions among the configurations of the colony are obtained. A sequence of transitions is a computation which is halting if it reaches a configuration where no cell can use any program. The result of a halting computation is obtained from the number of copies of objects from Fpresent in the environment in the halting configuration. Because of the non-determinism in choosing the programs, several computations can be obtained from a given initial configuration, hence with a P colony Πwe can associate a set of vectors of non-negative integers computed by all possible halting computations of Π. Initially, the environment contains arbitrarily many copies of the environmental object e, and the cells also contain one or two copies of einside, depending on the capacity of the P colony. For a P colony Π= (V, e, F, C1, . . . , Cn) as above, a configuration can be formally written as an (n+ 1)-tuple (w1, . . . , wn;wE), where wi∈V∗represents the multiset of objects from cell Ci,1≤i≤n, and wE∈(V− {e})∗represents the multiset of objects from the environment different from the environmental object e. The initial configuration is (ei, . . . , ei;ε) where i∈ {1,2}is the capacity of the cells. A transition from a configuration to another is denoted as (w1, . . . , wn;wE)⇒(w0 1, . . . , w0 n;w0 E) where w0 Eand each w0 iis obtained from wi,1≤i≤nby executing one of the programs of Pi. The set of vectors in Nm,m=|F|,F={o1, . . . , om}computed by a P colony Πis defined as N(Π) = {(|vE|o1, . . . , |vE|om)|(ei, . . . , ei;ε)⇒∗(v1, . . . , vn, vE)} where (ei, . . . , ei, ε), i∈ {1,2}, is the initial configuration, (v1, . . . , vn, vE) is a halting configuration, and ⇒∗denotes the reflexive and transitive closure of ⇒. Let us denote by PCOL(i, j, k, check) and PCOL(i, j, k, no-check) the classes of sets of vectors generated by P colonies with j≥1 cells of capacity i∈ {1,2}, having at most k≥1 programs associated to a cell which contain or do not contain On Very Simple P Colonies 101 checking rules, respectively. If a numerical parameter is unbounded, we denote it by a ∗. P colonies can simulate register machines with a rather limited number of programs per cell. In [3], it was shown that PCOL(2,∗,4, check) = PCOL(3,∗,3, check) = NRE where NRE denotes the class of recursively enumerable sets of integer vectors. Even one cell is enough, if it may have an arbitrarily large number of programs, that is, PCOL(2,1,∗, check) = NRE. Similar results were also obtained without the use of checking rules. In this case we have PCOL(2,∗,8, no-check) = PCOL(3,∗,7, no-check) = NRE. 3 P Colonies with One Object In [1] it was shown that if checking rules are allowed to be used, then all recursively enumerable sets of vectors can even be generated by P colonies with capacity one, that is, PCOL(1,4,∗, check) = NRE. In the following we strengthen this result by showing that P colonies with six components generate all vectors even if checking rules are not used. Theorem 1. PCOL(1,6,∗, no-check) = NRE. Proof. We construct a P colony simulating the computations of a register machine. Let us consider an m-register machine M= (m, H, l0, lh, P ) and represent the content of the register iby the number of copies of a specific object aiin the environment. We construct the P colony Π= (V, e, F, C1, . . . , C6) with: V={li, l0 i, l00 i,¯ li, Ki, Li, L0 i, L00 i, L000 i, Ei, Fi,$i|for each li∈H} ∪ {ai, ai,j |1≤i≤m, 1≤j≤ |H|} ∪ {D, D0, T}, F={ai|register iis an output register},and Ci= (e, Pi),for 1 ≤i≤6. Because initially there are only copies of ein the environment and inside the cells, we have to initialize the simulation of the computation of Mby generating the initial the label l0, and an arbitrary number of l0 i, l00 ifor all li∈H. These symbols are generated by C1and C2with the following programs: P1⊃ {he→l0 ri,hl0 r↔ei,he→l00 ri,hl00 r↔ei | lr∈H} ∪ {he↔D0i,hD0→l0i,hl0↔Di}, P2⊃ {he→D0i,hD0→D0i,hD0↔l0 1i,hl0 1→Di,hD↔l00 1i}. 102 L. Ciencialov´a et al. With these programs, from the configuration (e, e, e, e, e, e;ε), we obtain (D, l00 1, e, e, e, e;l0w) where the environment contains the label of the initial instruction, l0, and w, a multiset of primed and double primed instruction labels. To simulate the instruction li: (ADD(r), lj, lk), cells C1and C3cooperate to add one copy of object arand object ljor lkto the environment. P1:P3 i1:hD↔ar,iii1:he↔lii i2:har,i →arii2:hli→ar,ii i3:har↔Kjii3:har,i ↔l0 ii i4:har↔Kkii4:har,i →ti i5:hKj→ljii5:hl0 i→Kji i6:hKk→lkii6:hl0 i→Kki i7:hlj↔Dii7:hKj↔ei i8:hlk↔Dii8:hKk↔ei i9:ht→ti It is not difficult to follow how the interplay of these two cells produce the configuration (D, l00 1, e, e, e, e;ljarw0) or (D, l00 1, e, e, e, e;lkarw0) from a configuration (D, l00 1, e, e, e, e;liw) where w, w0are multisets of l0 i, l00 ifor li∈Hand ar1≤r≤m. If there is no l0 ipresent in the environment when the program i3of cell C3should be used, then the programs i4and i9do not allow the halting of the computation. For each subtract instruction lf: (SUB(r), lg, ln) there are the following programs in P1,P4,P5and in P6: P1P4P5P6 f1:hD↔Lfif1:he↔lfif1:he↔L0 fif1:he↔L00 fi f2:hLf→Efif2:hlf→Lfif2:hL0 f→l0 fif2:hL00 f→l0 fi f3:hEf→Ffif3:hLf↔l0 fif3:hl0 f↔arif3:hl0 f↔$fi f4:hFf→$fif4:hl0 f→L0 fif4:hl0 f↔$fif4:h$f→lgi f5:h$f↔Dif5:hL0 f↔l00 fif5:h$f→¯ lnif5:hlg↔ei f6:hl00 f→L000 fif6:har→eif6:hl0 f↔¯ lni f7:hL000 f→L00 fif7:h¯ ln↔eif7:h¯ ln→lni f8:hL00 f↔eif8:hln↔ei f9:hLf→ti f10 :hL0 f→ti f11 :ht→ti In the following table we show how a subtract instruction can be simulated by the programs above. Since C2and C3cannot apply any of their rules in any step of the following simulation, we omit them from the table. The multiset of objects in the environment is denoted by [. . .], and for now we assume that it always contains a sufficient amount of l0 i, l00 iobjects for any li∈H. First we consider the case when there is at least one object arin the environment, that is, if the simulation starts in a configuration (D, l00 1, e, e, e, e;lfar[. . .]). On Very Simple P Colonies 103 configuration of Πprograms to be applied C1C4C5C6Env P1P4P5P6 1. D e e e lfar[. . .]−f1− − 2. D lfe e ar[. . .]−f2− − 3. D Lfe e ar[. . .]−f3− − 4. D l0 fe e Lfar[. . .]f1f4− − 5. LfL0 fe e Dar[. . .]f2f5− − 6. Efl00 fe e L0 fDar[. . .]f3f6f1− 7. FfL000 fL0 fe Dar[. . .]f4f7f2− 8.$fL00 fl0 fe Dar[. . .]f5f8f3− 9. D e are$fL00 f[. . .]− − f6f1 10. D e e L00 f$f[. . .]− − − f2 11. D e e l0 f$f[. . .]− − − f3 12. D e e $f[. . .]− − − f4 13. D e e lg[. . .]− − − f5 14. D e e e lg[. . .]−g1− − In 13 steps we obtain from a configuration (D, l00 1, e, e, e, e;lfar[. . .]) a new one (D, l00 1, e, e, e, e;lg[. . .]) where lgis the label of the instruction which should follow the successful decrease of the value of the nonempty register r, and the environment contains a multiset of objects l0 i, l00 ifor li∈H. Now we consider the case when register r, which is the register to be decremented stores zero, that is, if the simulation starts in a configuration (D, l00 1, e, e, e, e;lf[. . .]) where the environment does not contain any object ar. configuration of Πprograms to be applied C1C4C5C6Env P1P4P5P6 1. D e e e lf[. . .]−f1− − 2. D lfe e [. . .]−f2− − 3. D Lfe e [. . .]−f3− − 4. D l0 fe e Lf[. . .]f1f4− − 5. LfL0 fe e D[. . .]f2f5− − 6. Efl00 fe e L0 fD[. . .]f3f6f1− 7. FfL000 fL0 fe D[. . .]f4f7f2− 8.$fL00 fl0 fe D[. . .]f5f8− − 9. D e l0 fe$fL00 f[. . .]− − f4f1 10. D e $fL00 f[. . .]− − f5f2 11. D e ¯ lnl0 f[. . .]− − f7− 12. D e e l0 f¯ ln[. . .]−−− f6 13. D e e ¯ ln[. . .]−−− f7 14. D e e ln[. . .]−−− f8 15. D e e e ln[. . .]−n1− − 104 L. Ciencialov´a et al. Similarly to the previous case, in 14 steps we obtain a configuration (D, l00 1, e, e, e, e;ln[. . .]) where lnis the label of the instruction which should follow lfif register ris empty, that is, if the decrease of its value is not possible. Consider now what happens if there is an insufficient amount of objects l0 i, l00 i for li∈His present in the environment. Notice that such symbols are needed in step 3 and 5 by cell C4. If there is no more available (not enough of them were produced in the initial phase by C1and C2), then the programs f9f10 and f11 do not allow the halting of the computation. From these considerations we can see that after the initialization phase, all instructions of the register machine Mcan be simulated by the P colony. If the label of the halt instruction, lhis produced, the computation halts since there is no program for processing the object lh. The reader can immediately see that Π computes the same set of vectors as M. 4 P Colonies with Senders and Consumers Now we continue with the investigation of two object P colonies with insertiondeletion programs. It is not too difficult to see that if we allow a cell to contain both types of programs, then we can simulate the other types of programs in two steps, thus, it is more interesting to consider P colonies having cells which contain either insertion or deletion programs, but not both types at the same time. We call these systems P colonies with senders and consumers. A sender is a cell with only insertion programs, a consumer is a cell with only deletion programs. Let us denote by PCOL(s-c, i, j) the class of sets of numbers generated by P colonies with senders and consumers having at most i≥1 cells with at most j≥1 program each. Example 1. (a) Every sender cell in a P colony can generate the Parikh set of a regular language L⊆T∗. Let G= (N, T, P, S) be a regular grammar such that L(G) = L. For accepting the Parikh vectors of the words in L, we use the programs he, out;e→eSi,he, out;S→aBi for each S→aB of P, and then hx, out;A→aBi, x ∈T for every A→aB in P. Finally, for every rule of the form A→awe need hx, out;A→aFi, x ∈T, ha, out;F→FF i, where F /∈T∪N. (b) Every consumer cell in a P colony can consume the Parikh set of a regular language L. To see this, let M= (Q, T, δ, q0, F) be a deterministic finite automaton such that L(M) = L. On Very Simple P Colonies 105 We need the program he, in;ee →q0i, and to every transition δ(qi, a) = qjin M ha, in;xqi→qji, x ∈T∪ {e}. If qj∈Fin δ(qi, a) = qjwe have to add the programs ha, in;xqi→Fi, x ∈T where F /∈Q∪T. Now we show that three cells, one sender and two consumers are sufficient to generate all recursively enumerable sets of integer vectors. Theorem 2. PCol(s-c,3,∗) = NRE. Proof. We simulate the computations of an m-register machine M= (m, H, l0, lh, P ), m ≥1,by representing the content of the register iby the number of copies of a specific object aiin the environment. We construct the P colony Π= (V, e, F, C1, C2, C3) with: V={l, l0, l00 , l000, liv, lv,¯ l, ¯ ¯ l|l∈H}∪{ai|1≤i≤m} ∪ {K, T1, T2, T3, T4, T5}, F={ai|register iis an output register},and Ci= (ee, Pi) for 1 ≤i≤3. The P colony Πstarts its computation in the initial configuration (ee, ee, ee;ε). We initialize the computation by generating the initial label l0with a program from P1, he, out;e→l0l0i ∈ P1 obtaining (l0l0, ee, ee;ε). The simulation of an instruction with label listarts from a configuration (lili, ee, ee;w) where w∈V∗, the multiset of objects in the environment, represents the counter contents of M. To simulate an ADD instruction, we use the programs of P1and P3. For each li, lj, lk∈Hwith libeing the label of an instruction li: (ADD(r), lj, lk), we have the following programs: P1P3 i1:hli, out;li→arljii1:hli, in;ee →T1i i2:hli, out;li→arlkii2:he, in;liT1→ei i3:har, out;lj→ljljii3:hli, in;¯ ¯ liT5→T1i i4:har, out;lk→lklki Using these programs, we obtain a sequence of configurations 106 L. Ciencialov´a et al. (lili, ee, ee;w)⇒(arl, ee, ee;liw)⇒(ll, ee, liT1;arw) where lis the label of the next instruction, that is, we either have (ljlj, ee, liT1;arw) or to (lklk, ee, liT1;arw). The contents of cell C3,liT1, will change in the next step to ee independently of the several ways of the continuation of the computation, as we shall see later. The program labeled with i3is used if the instruction simulated before liwas a SUB instruction (see below). In this case, the configuration in which the simulation of listarts is (lili, ee, ¯ liT4;¯ ¯ liw) and we need the steps (lili, ee, ¯ liT4;¯ ¯ liw)⇒ (arl, ee, ¯ ¯ liT5;liw)⇒(ll, ee, liT1;arw) and program i3to obtain the same configuration as before. Now we show how to simulate a SUB instruction. For each lj, lk, ll∈Hwith ljbeing the label of an instruction lj: (SUB(r), lk, ll), and for all labels lr∈H, we have the following programs. P1P2P3 j1:hlj, out;lj→l0 jl0 jij1:hlj, in;ee →eij1:hl0 j, in;ee →T1i j2:hl0 j, out;l0 j→l00 jl00 jij2:har, in;elj→eij2:he, in;l0 jT1→T2i j3:hl00 j, out;l00 j→l000 jliv jij3:hl00 j, in;elj→eij3:hl00 j, in;eT2→T3i j4:hl000 j, out;liv j→¯ lk¯ lkij4:hl000 j, in;are→eij4,r :h¯ lr, in;l00 jT3→T4i j5:hliv j, out;l000 j→¯ ll¯ llij5:he, in;l000 je→eij5,r :h¯ lr, in;eT2→T4i j6:h¯ lk, out;¯ lk→¯ ¯ lk¯ ¯ lkij6:hliv j, in;are→Kij6,r :h¯ ¯ lr, in;¯ lrT4→T5i j7:h¯ ¯ lk, out;¯ ¯ lk→lklkij7:he, in;liv jK→Kij7,r :he, in;¯ ¯ lrT5→ei j8:h¯ ll, out;¯ ll→¯ ¯ ll¯ ¯ llij8:he, in;eK →Ki j9:h¯ ¯ ll, out;¯ ¯ lk→llllij9:hl000 j, in;l00 je→Ki j10 :he, in;l000 jK→Ki j11 :hliv j, in;l00 je→ei j12 :he, in;liv je→ei In the following table we show how the programs above simulate the execution of the instruction lj: (SUB(r), lk, ll). To save space, we use the sign “/” to separate the different possible multisets which might appear in the same row of the table. First we consider the case when register ris not empty, that is, when there is at least one object arpresent in the environment. On Very Simple P Colonies 107 configuration of Πprograms to be applied C1C2C3Env P1P2P3 1. ljljee ?arw0j1−? 2. l0 jl0 jee ?ljarw00 j2j1? 3. l00 jl00 jlje ee l0 jarw j3j2j1 4. l000 jliv jare l0 jT1l00 jw j4/j5−j2 5.¯ lk¯ lk/¯ ll¯ llare eT2(l000 j/liv j)l00 jw j6/j8j4/j6j3 6.¯ ¯ lk¯ ¯ lk/¯ ¯ ll¯ ¯ lll000 je/liv jK l00 jT3(¯ lk/¯ ll)w j7/j9j5/j7j4,k/j4,l 7. lklk/llllee/eK (¯ lk/¯ ll)T4(¯ ¯ lk/¯ ¯ ll)w k1/l1−/j8j6,k/j6,l 8. l0 kl0 k/l0 ll0 lee/eK (¯ ¯ lk/¯ ¯ ll)T5(lk/ll)w k2/l2k1/j8j7,k/j7,l 9. l00 kl00 k/l00 ll00 l(lk/ll)e/eK ee (l0 k/l0 l)w k3/l3k2/j8j1 We see that starting with a configuration where C1contains the objects ljljand the environment contains ar, in six steps we obtain a configuration where the object aris removed from the environment, and C1either contains the label of the next instruction lk, or because of the presence of program j8, in P2, the computation will never be able to halt. Now we show the simulation of the lj: (SUB(r), lk, ll) instruction when there is no object aris present in the environment, that is, when register ris empty. configuration of Πrules to be applied C1C2C3Env P1P2P3 1. ljljee ?w j1−? 2. l0 jl0 jee ?ljw j2j1? 3. l00 jl00 jlje ee l0 jw j3−j1 4. l000 jliv jlje l0 jT1l00 jw j4/j5j3j2 5.¯ lk¯ lk/¯ ll¯ lll00 je eT2(l000 j/liv j)w j6/j8j9/j11 − 6.¯ ¯ lk¯ ¯ lk/¯ ¯ ll¯ ¯ lll000 jK/liv je eT2(¯ lk/¯ ll)w j7/j9j10/j12 j5,k/j5,l 7. lklk/lllleK/ee (¯ lk/¯ ll)T4(¯ ¯ lk/¯ ¯ ll)w k1/l1j8/−j6,k/j6,l 8. l0 kl0 k/l0 ll0 leK/ee (¯ ¯ lk/¯ ¯ ll)T5(lk/ll)w k2/l2j8/k1j7,k/j7,l 9. l00 kl00 k/l00 ll00 leK/(lk/ll)e ee (l0 k/l0 l)w k3/l3j8/k2j1 In this case, similarly to the previous one, we either get the objects lklkin the cell C1, or the computation will not be able to halt. The rules to be applied and the objects contained by the cell C3in row 1. and row 2. of the tables above depend on the instruction liwhich was simulated before lj. If liis an ADD instruction, then we have liT1in the first row, and applying the program i2from P3we get ee in the second row, where no program is applied until the next step. Also, w=w0=w00 in this case. If liis a SUB instruction, then (as we can also see from row 7. and row 8.) the contents of the cell C3is ¯ ljT4and ¯ ¯ ljT5in the first two rows where the programs i6,j and i7,j are applied. In this case w00 =¯ ¯ ljw, and w0=w. 114 D. D´ıaz et al. Nand computable in polynomial time. Let us denote by u= (n, (w1,...,wn), k), where wi=w(ai), 1 ≤i≤n, the given instance of the problem. We define the polynomially computable function s(u) = g(n, k). We will provide a family of tissue P systems where each P system solves all the instances of the SUBSET SUM problem with the same size. The weight function wof the concrete instance will be provided via an input multiset determined via the function cod(u) = {{vj i:w(ai) = j∧1≤i≤n}} ∪ {{qk}}, where vj i(i.e., j copies of object vi) represents that jis the weight of the element ai. Next, we will provide a family of recognizer tissue P systems with cell division which solve the SUBSET SUM problem in linear time. For each (n, k)∈N2we will consider the system Π(n, k) = (Γ, Σ, ω1, ω2,R,E, iin, i0), where •Γ=Σ(n)∪ {Ai, Bi|1≤i≤n} ∪ {ai|1≤i≤n+⌈log n⌉+⌈log(k+ 1)⌉+ 11} ∪ {ci|1≤i≤n+ 1} ∪ {di|1≤i≤ ⌈log n⌉+⌈log(k+ 1)⌉+ 4} ∪ {ei|1≤i≤ ⌈log n⌉+ 1} ∪ {Bij |1≤i≤n∧1≤j≤ ⌈log(k+ 1)⌉+ 1} ∪ {b, D, p, q, g1, g2, f1, T, S, N, yes,no} •Σ={vi|1≤i≤n} •ω1=a1b c1yes no •ω2=DA1···An • R is the following set of rules: 1. Division rules: r1,i ≡[Ai]2→[Bi]2[λ]2for i= 1,...,n 2. Communication rules: r2,i ≡(1, ai/ai+1,0) for i= 1,...,n+⌈log n⌉+⌈log(k+ 1)⌉+ 10 r3,i ≡(1, ci/c2 i+1,0) for i= 1,...,n r4≡(1, cn+1/D, 2) r5≡(2, cn+1/d1e1,0) r6,i ≡(2, ei/e2 i+1,0) for i= 1,...,⌈log n⌉ r7,i ≡(2, di/di+1,0) for i= 1,...,⌈log n⌉+⌈log(k+ 1)⌉+ 3 r8,i ≡(2, e⌈log n⌉+1Bi/Bi1,0) for i= 1,...,n r9,i,j ≡(2, Bij/B2 ij+1,0) for i= 1,...,n,j= 1,...,⌈log(k+ 1)⌉ r10,i ≡(2, Bi⌈log(k+1)⌉+1vi/p, 0) for i= 1,...,n r11 ≡(2, pq/λ, 0) r12 ≡(2, d⌈log n⌉+⌈log(k+1)⌉+4/g1f1,0) r13 ≡(2, f1p/λ, 0) r14 ≡(2, f1q/λ, 0) r15 ≡(2, g1/g2,0) r16 ≡(2, g2f1/T, 0) r17 ≡(2, T/λ, 1) r18 ≡(1, bT/S, 0) r19 ≡(1, Syes/λ, 0) r20 ≡(1, an+⌈log n⌉+⌈log(k+1)⌉+11b/N, 0) Cell-like vs. Tissue-like P Systems 115 r21 ≡(1, Nno/λ, 0) • E =Γ− {yes,no} •iin = 2, is the input cell •i0=env, is the output cell An overview of the computation and more details of the design can be read in [2]. 4 Sevilla Carpets Sevilla Carpets were presented in [1] as an extension of the Szilard language, which consists of all strings of rule labels describing correct derivations in a given grammar (see e.g., [6, 7] or [11]). The Szilard language is usually defined for grammars in the Chomsky hierarchy where only a single rule is used in each derivation step, so a derivation can be represented as the string of the labels of the rules used in the derivation (the labeling is supposed to be one-to-one). Sevilla Carpets are a Szilard-way to describe a computation in a P system. The main difference is that a multiset of rules can be used in each evolution step of a P system. In [1] a bidimensional writing is proposed to describe a computation of a P system. The (Sevilla) Carpet associated with a computation of a P system is a table with the time on the horizontal axis and the rules explicitly mentioned along the vertical axis; then, for each rule, in each step, a piece of information is given. Depending on the amount of information given to describe the evolution, Ciobanu, P˘aun and S¸tef˘anescu propose five variants for the Sevilla Carpets: 1. Specifying in each time unit for each membrane whether at least one rule was used in its region or not; 2. Specifying in each time unit for each rule whether it was used or not; 3. Mentioning in each time unit the number of applications of each rule; this is 0 when the rule is not used and can be arbitrarily large when the rules are dealing with arbitrarily large multisets; 4. We can also distinguish three cases: that a rule cannot be used, that a rule can be used but it is not because of the nondeterministic choice and that a rule is actually used; 5. A further possibility is to assign a cost to each rule, and to multiply the number of times a rule is used with its cost. They also propose two parameters (weight and surface) to study Sevilla Carpets. In [4] two new parameters (height and average weight) were proposed. 4.1 Parameters for the Descriptive Complexity Many times we will not be interested only in the number of cellular steps of the computation, but also in other type of resources required to perform the computation. Specially if we want to implement in silico a P system, we need to be 116 D. D´ıaz et al. careful with the number of times that a rule is applied, maybe with the number of membranes and/or the number of objects present in a given configuration. In order to describe the complexity of the computation, the following parameters are proposed: •Weight: It is defined in [1] as the sum of all the elements in the carpet, i.e., as the total number of applications of rules along the computation. The application of a rule has a cost and the weight measures the total cost of the computation. •Surface: It is the multiplication of the number of steps by the total number of the rules used by the P system. It can be considered as the potential size of the computation. From a computational point of view we are not only interested on P systems which halt in a small number of steps, but in P systems which use a small amount of resources. The surface measures the resources used in the design of the P system. Graphically, it represents the surface where the Sevilla Carpet lies on. •Height: It is the maximum number of applications of any rule in a step along the computation. Graphically, it represents the highest point reached by the Sevilla Carpet. •Average Weight: It is calculated by dividing the weight to the surface of the Sevilla Carpet. This concept provides a relation between both parameters which gives an index on how the P system exploits its massive parallelism. 5 Comparing the Solutions In [4], two uniform families of P systems with active membranes solving the Subset Sum were presented. In both solutions, a tuple (n, (w1,...,wn), k) is used to represent an instance of the problem, where nstands for the size of A={a1,...,an}, wi=w(ai), and kis the constant given as input for the problem. Both solutions are based on a brute force algorithm implemented in the framework of P systems with active membranes. The idea of the design can be divided into several stages: •Generation stage: for every subset of A, a membrane is generated via membrane division. •Weight calculation stage: in each membrane the weight of the associated subset is calculated. This stage will take place in parallel with the previous one. •Checking stage: in each membrane it is checked whether or not the weight of its associated subset is exactly k. This stage cannot start in a membrane before the previous ones are over in that membrane. •Output stage: when the previous stage has been completed in all membranes, the system sends out the answer to the environment. The first family can be found in [9]. Let us recall that the instance u= (n, (w1,...,wn), k) is processed by the P system Π1(hn, ki) with input the multiset xw1 1xw2 2. . . xwn n. Cell-like vs. Tissue-like P Systems 117 This design depends on the two constants that are given as input in the problem: nand k. It consists on 5n+ 5k+ 18 evolution rules, and if an appropriate input multiset is introduced inside membrane ebefore starting the computation, the system will stop and output an answer in 2n+ 2k+ 6 steps (if the answer is No) or in 2n+ 2k+ 5 steps (if the answer is Y es). The second family is inspired in the previous one. Some modifications were made following the design presented in [3]. In this solution the instance u= (n, (w1,...,wn), k) is processed by the P system Π2(n) with input the multiset xw1 1xw2 2. . . xwn n. The above design depends only on one of the constants that are given as input in the problem: n. It is quite similar to the previous one, the difference lies in the checking stage and the answer stage. In this case we avoid the use of counters that require knowing the constant k. The number of evolution rules is 5n+ 41, and the number of steps of the computation depends on the concrete instance that we need to solve, but it is linearly bounded. We compare these solutions with the solution described in Section 3. As pointed out in [2], the number of rules for a set A={a1...,an}of size nis . . . and the number of steps is ... if the answer is Yes and ... if the answer is No. 5.1 Descriptive Complexity We present some detailed statistics about the previous designs, trying to compare them on a more general basis than just looking the number of steps that the computation performs. Following this scheme, we present the Sevilla Carpets associated with the computations of the three different solutions to the Subset Sum problem working on the same instance: u= (5,(3,5,3,2,5),9). That is, n= 5, k= 9 and the list of weights is w1= 3, w2= 5, w3= 3, w4= 2, w5= 5. The P system Π1(h5,9i) has 88 evolution rules, and all of them are applied with the exception of the rules: [q19]− e→[ ]0 eY es, [q3]− e→[ ]− e#, [q9]− e→[ ]− e# and [Y es]− s→[ ]0 sY es. The P system Π1(5,9) stops at step 33 and sends an object No to the environment. The weight of the Sevilla Carpet (the total number of rule applications along the computation) is 2179. The height of the Sevilla Carpet (the maximal number of times that a rule is applied in one evolution step) is 82 and it is reached at Step 9. The surface of the Sevilla Carpet is 2904. The average weight of the Sevilla Carpet is 0.749656 The P system Π2(5) has 65 evolution rules, and all of them are applied with the exception of the rules: [q3]0 e→[ ]+ eY es and [Y es]− s→[ ]0 sY es. The P system Π2(5) stops at step 38 and sends an object No to the environment. The weight of the Sevilla Carpet is 3368. The height of the Sevilla Carpet is 108 and it is reached at step 10. The surface of the Sevilla Carpet is 2470. The average weight of the Sevilla Carpet is 1.36275 Finally, the solution with tissue-like P systems with cell division has 88 rules and 84 of them are applied in this computation. The P system stops at step 24. 118 D. D´ıaz et al. 0 10 20 30 40 50 60 70 80 90 Rules 0 5 10 15 20 25 30 35 Steps -25 0 25 50 75 100 Fig. 1. Sevilla Carpet for solution 1 The surface of the Sevilla Carpet is 2112 and its weight is 2405. The height is 128 and it is reached at steps 10, 12, 13, 14 and 15. The average weight of the Sevilla Carpet is 1.13873. The following table shows the parameters of both solutions: Sol. 1 Sol.2 Sol. 3 Rules 88 65 88 Steps 33 38 24 Surface 2904 2470 2112 Weight 2179 3368 2405 Height 82 108 128 Average Weight 0.749656 1.36275 1.13873 If we consider the number of steps as a complexity measure to compare the designs, then we conclude that the third solution is better than the other ones, since it needs less steps. Moreover, concerning the weight of the Sevilla Carpet, solution 1 is better than the other ones, because it uses less resources during the computation. Nonetheless, the key point of a design of a solution in Membrane Computing is the use of the massive parallelism. As pointed out in [5], a bad design of a P system consists of a P system which does not exploit its parallelism, that is, working as a sequential machine: in each step only Cell-like vs. Tissue-like P Systems 119 0 10 20 30 40 50 60 70 Rules 0 5 10 15 20 25 30 35 40 Steps -25 0 25 50 75 100 125 Fig. 2. Sevilla Carpet for solution 2 one object evolve in one membrane whereas the remaining objects do not evolve. On the other hand, a good design consists of a P system in which a huge amount of objects are evolving simultaneously in all membranes. If both P systems perform the same task, it is obvious that the second one is a better design that the first one. In this line, the fact that the average weight of solution 2 is larger than the average weight of the other solutions can be interpreted saying that the second design makes a better use of the parallelism in P systems. 6 Conclusions and Future Work It is important to remark that these are not asymptotical comparisons, as we focus only on the data corresponding to one instance. Indeed, due to the exponential number of membranes created during the generation stage, we believe that considering another instance with a greater size will stress the differences between the design based only on nand the other one, based on nand k. The bound on the size of the instances that can be studied is imposed by the necessity to use a P systems simulator to obtain the detailed description of the computation: number of rules, number of cellular steps, and number of times that the rules are applied in each step. 120 D. D´ıaz et al. 0 10 20 30 40 50 60 70 80 90 Rules 0 5 10 15 20 25 Steps -25 0 25 50 75 100 125 Fig. 3. Sevilla Carpet for solution 3 Acknowledgements The authors acknowledge the support of the project TIN2006-13425 of the Ministerio de Educaci´on y Ciencia of Spain, cofinanced by FEDER funds, and the support of the Project of Excellence with Investigador de Reconocida Val´ıa of the Junta de Andaluc´ıa, grant P08-TIC-04200. References 1. G. Ciobanu, Gh. P˘aun, Gh. S¸tef˘anescu: Sevilla Carpets Associated with P Systems. In M. Cavaliere, C. Mart´ın–Vide and Gh. P˘aun (eds.), Proceedings of the Brainstorming Week on Membrane Computing, Tarragona, Spain, 2003, Report RGML 26/03, 135–140. 2. D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Solving Subset Sum in Linear Time by Using Tissue P Systems with Cell Division. In Bio-inspired Modeling of cognitive tasks, J. Mira and J.R. Alvarez, eds., LNCS 4527, Springer, 2007, 170–179. 3. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Towards a programming language in cellular computing. Proceedings of the 11th Workshop on Logic, Language, Information and Computation (WoLLIC’2004), July 19-22, 2004, 1-16 Campus de Univ. Paris 12, Paris, France. A preliminary version in Gh. P˘aun, A. Riscos, A. Romero, F. Sancho, eds., Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, 2004, 247–257. Cell-like vs. Tissue-like P Systems 121 4. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: On Descriptive Complexity of P Systems. In G. Mauri, Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg, A. Salomaa, eds., Membrane Computing. LNCS 3365, Springer, 2005, 320–330. 5. M. A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: On the Degree of Parallelism in Membrane Systems. Theoretical Computer Science, 372, 2-3 (2007), 183–195. 6. E. M¨akinen: A Bibliography on Szilard Languages, Dept. of Computer and Information Sciences, University of Tampere, http://www.cs.uta.fi/reports/ pdf/Szilard.pdf. 7. A. Mateescu, A. Salomaa: Aspects of Classical Language Theory. In G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages (vol. 1), Springer, Berlin, 1997. 8. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Tissue P System with cell division. In Gh. P˘aun, A. Riscos-N´u˜nez, A. Romero-Jim´enez, F. Sancho-Caparrini, eds., Second Brainstorming Week on Membrane Computing, Sevilla, Report RGNC 01/2004, 2004, 380–386. 9. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Solving the Subset Sum Problem by Active Membranes. New Generation Computing, 23, 4 (2005), 367–384. 10. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: A polynomial complexity class in P systems using membrane division. In E. Csuhaj-Varj´u, C. Kintala, D. Wotschke, Gy. Vaszyl, eds., Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, 2003, 284–294. 11. A. Salomaa: Formal Languages. Academic Press, New York, 1973. P Systems and Topology: Some Suggestions for Research Pierluigi Frisco School of Mathematical and Computer Sciences, Heriot-Watt University EH14 4AS Edinburgh, UK [email protected] Summary. Lately, some studies linked the computational power of abstract computing systems based on multiset rewriting to Petri nets and the computation power of these nets to their topology. In turn, the computational power of these abstract computing devices can be understood just looking at their topology, that is, information flow. This line of research is very promising for several aspects: its results are valid for a broad range of systems based on multiset rewriting; it allows to know the computational power of abstract computing devices without tedious proofs based on simulations; it links computational power to topology and, in this way, it opens a broad range of questions. In this note we summarize the known result on this topic and we list a few suggestions for research together with the relevance of possible outcomes. 1 Introduction Imagine that a computing device based on multiset rewriting is defined. Let us call this computing device S1. This could be a P system with symport/antiport, or with catalysts, of with conformons, or it could be a definition of Diophantine equations, or some model of Brane calculi of whatever else you like. What would you do in order to know the computing power of such a system? Probably you would try to simulate with S1another computing system, say S2with known computational power. If this is possible, than you can say that S1 can compute at least as much as S2can compute. Then you would probably try to simulate S1with S2, if this is possible, then you know that the two systems have the same computational power. This is the standard way to know the computational power of a computing system. There is another way to know the computational power of S1. This new way is based on the fact that a computing system has a way to store information and a way to manipulate it. This other way looks at how such a system stores information 130 P. Frisco Suggestion for research 1 Define a model of P systems with catalysts having computational power equivalent to the one of restricted register machines. Line 6 in Table 1 refers to the class of numbers accepted by P/T systems composed only by join and having a finite number of places when they run according to SCG. This class of number, called Jin [7], is well defined: it is proved that this kind of P/T systems can only accept J. What it is not well known is how Jrelates to other classes of numbers. Suggestion for research 2 As indicated in Table 1, it is known that N·REG ⊂ J⊂N·CS. Restrict this (rather broad) interval. A solution to this suggestion does not necessarily mean to have a result of the kind: A⊂J⊂Bwhere Aand Bare classes of numbers. The indication of what part of N·CS is in Jand what not, would be already of interest. In the Introduction we said: “it shows how to know the computing power of a formal system based on multiset rewriting without running simulations but simply looking at the kind of operations that the formal system can perform”. What do we mean with ‘looking’? In this case ‘looking’ means the way Definition 1 is implemented, that is what it is considered as configuration of the simulated system. Given a configuration of a formal system it is possible to ‘look’ at it in different ways. For instance, we could ignore some elements in the configuration, we could group different elements in the configuration, etc. This concept of ‘looking’ (observing) has been formalized (see, for instance, [1]). As a consequence of this, given a formal system, we could implement Definition 1 in different ways, leading to different models of Petri nets and, possibly, to different accepted/generated languages. Suggestion for research 3 Study how different implementations of Definition 1 in a given formal system change the class of numbers accepted/generated by it. Is it possible to link these results to the topology as presented in this paper? The previous suggestion for research can go beyond the study of a few formal systems ‘observed’ in different ways. It can include more general studies as the classification of systems that can be ‘observed’ in only one way, or in an unbounded number of ways, or that can accept/generate the same language independently of the way they are observed, etc. For instance, we could obtain results of the kind: the ‘observation’ of the systems in row 4 of Table 1 can only accept/generate finite classes of numbers, etc. If we look at rows 2 and 3 in Table 1 you notice that the difference on the accepted class of numbers is due to the allowed composition. Here one could imagine that if the composition would be something in between what present in these two rows, then the accepted language would also be ‘in between’. We try to clarify this point. In row 2 we deal with systems in which join and fork can only be in sequence as in Fig. 3.a, while in row 3 we deal with systems in which the two building blocks can be composed in any way. What language can be accepted by P Systems and Topology: Some Suggestions for Research 131 P/T systems having a finite number of join and fork in which only a few are in sequence as in Fig. 3.a? This line of research could be called “language generated by pseudo-random Petri nets” where ‘random’ refers to the fact that the Petri net is created composing building blocks in a random way, while ‘pseudo’ refers to the fact that we impose some limitations to this randomness as, for instance, the fact that a few join and fork have to be in a specific sequence. Suggestion for research 4 Study languages generated by pseudo-random Petri nets. This line of research requires the creation of some computer programs (or the use of already available computer programs). Of course, a similar line of research can be pursued for P systems and any other kind of computing device that can be build in a pseudo-random way. In Section 6 we indicated how the results in Table 1 have been used on P systems with catalysts. We tried to use similar results on other models of P systems (symport/antiport, conformons, etc., see [6]) and all went as we expected. This means that using Definition 1 and the results in Table 1 we obtained results similar, in terms of descriptional complexity, to the ones already known. The exception to this were spiking P systems. We did not succeed in defining a simulation (as in Definition 1) that let us re-obtain the known results on this model of P systems with the same descriptional complexity. The results we got needed more features (more compartments, the presence of forgetting rules, etc.) not present in direct proofs. This fact is particularly intriguing because it could suggest some limits in the approach considered in this note. For this reason we propose: Suggestion for research 5 Use the approach considered in this paper on spiking P systems, analyzing advantages and limitations of it. Only row 2 in Table 1 considers P/T system in which the underlying net has one kind of limitations in its composition. What about other limitations in the arrangement? Suggestion for research 6 Study further the computational power of P/T systems whose relative arrangement of pairs of fork and join is limited. In particular one could focus on the limitations needed to generate semilinear sets. The relevance of the following suggestion should be straightforward: Suggestion for research 7 Are join and fork the only building blocks that lead to the result in Table 1? Are there other building blocks leading to the same or different results? The overall aim of the approach considered in this paper is: 132 P. Frisco Suggestion for research 8 Create a full hierarchies of accepting and generating computational processes in terms of sets of building blocks, compositions of elements in these sets and the functions Wand K(present in the definition of P/T systems in [13, 5]). References 1. M. Cavaliere: Computing by observing: A brief survey. In A. Beckmann, C. Dimitracopoulos, B. L¨owe, editors, Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008, Athens, Greece, June 15-20, 2008, Proceedings, volume 5028 of Lecture Notes in Computer Science. Springer, Berlin, 2008. 2. R. Freund, L. Kari, M. Oswald, P. Sos´ık: Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science, 330, 2 (2005), 251–266. 3. R. Freund, G. Lojka, M. Oswald, G. P˘aun, eds.: Membrane Computing. 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers, volume 3850 of Lecture Notes in Computer Science. Springer, Berlin, 2006. 4. P. Frisco: P systems, Petri nets, and Program machines. In Freund et al. [3], 209–223. 5. P. Frisco: A hierarchy of computational processes. Technical report, Heriot- Watt University, 2008. HW-MACS-TR-0059 http://www.macs.hw.ac.uk:8080/ techreps/index.html. 6. P. Frisco: Computing with Cells. Advances in Membrane Computing. Oxford University Press, 2009. to appear. 7. P. Frisco: On languages accepted by P/T systems composed by join. Technical report, Heriot-Watt University, 2009. HW-MACS-TR-0064 http://www.macs. hw.ac.uk:8080/techreps/index.html. 8. S.A. Greibach: Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7 (1978), 311–324. 9. O.H. Ibarra: On membrane hierarchy in P systems. Theoretical Computer Science, 334 (2005), 115–129. 10. O.H. Ibarra, H.-C. Yen: Deterministic catalytic systems are not universal. Theoretical Computer Science, 363, 2 (2006), 149–161. 11. R. Milner: Communication and Concurrency. Prentice-Hall, Englewood, N.J., 1989. 12. R. Milner: Communicating and Mobile Systems: the π-calculus. Cambridge University press, 1999. 13. W. Reisig, G. Rozenberg, eds.: Lectures on Petri Nets I: Basic Models, volume 1491 of Lecture Notes in Computer Science. Springer, Berlin, 1998. 14. G. Rozenberg, J. Engelfriet: Elementary net systems, pages 12–121. Volume 1491 of Reisig and Rozenberg [13], 1998. 15. G. Rozenberg, A. Salomaa: Handbook of Formal Languages. Springer, Berlin, 1996. Modeling Reaction Kinetics in Low-dimensional Environments with Conformon P Systems: Comparison with Cellular Automata and New Rate Laws Pierluigi Frisco1, Ramon Grima2 1School of Mathematics and Computer Sciences Heriot-Watt University, Edinburgh, UK [email protected] 2School of Biological Sciences University of Edinburgh, UK [email protected] Summary. Recently it has been shown that simulations of complex biological systems using conformon P systems and cellular automata do not necessarily give the same predictions. To further elucidate these differences we simulate a simple model of intracellular reactions involving a single bimolecular reaction occurring on a biological membrane using conformon P systems. We find that the predictions broadly agree with results from both the theory of random walks in low-dimensional environments and with previously published simulations using cellular automata. Moreover, a re-analysis of the data enables us to deduce novel rate laws for the kinetics of reactions occurring on biological membranes. 1 Introduction A recent publication [3] reported that simulations of HIV dynamics differ in their results according to the simulation platform used. In particular it is found that cellular automata (CA) models produce qualitatively correct dynamics only for a narrow range of rule probabilities and for particular initial conditions whereas conformon P (cP) models [2] derived from the CA model display significant robustness of qualitatively correct dynamics over a wide range of conditions. Presently the reasons for these differences are not understood. The complexity of the system under study precludes a rigorous analysis of these discrepancies. In this paper we consider a much simpler biological process at the base of an simpler model. For such model its rigorous analytical results are known for some cases. The paper is divided as follows: in Section 2 we describe the biology behind the model and its implementation using CA and cP, in Section 3 we analyze the 134 P. Frisco, R. Grima data generated by cP, compare with theory and CA results and also deduce some new biologically relevant kinetic laws and in Section 4 we draw some conclusion. 2 A Simple Biological Model: Implementation Using CA and cP There is growing evidence of the importance of reaction kinetics for the structural organization of the intracellular environment, which is far from the homogeneous, well mixed solution typical of in vitro experiments. A high degree of molecular crowding as well as the presence of indigenous obstacles in cellular media have important consequences in the physico-chemistry of the cell. The consequences of this in some process are only now becoming to be more generally understood. One of these consequences is that it is not clear what are the rate laws governing reactions occurring in vivo [7]. To tackle this problem biochemists have been using various computational frameworks to extract rate laws or empirical reaction equations from direct numerical simulations. Among these approaches, simulations based on CA are the most popular (see, for example, [5]). The biological process we considered in our investigations regards biochemical reactions occurring on cell membranes. It in known that about half of the proteins inside cells are membrane-associated [8] and thus biochemical reactions must necessarily function within the constraints imposed by the two-dimensional environment of the biological membrane. Prominent examples of such reactions are those involving enzymes called lipases which play key roles in fat metabolism and digestion and which occur on two-dimensional interfaces rather than in threedimensional solution. The simplest model of such dimensionally-restricted reaction kinetics consists of two types of particles, denoted with Aand B, which perform random walks on a two-dimensional plane and which upon encounter react with some probability and produce a single new inert particle C. This mathematical construct represents the physical process of the reaction of two molecules of two different types which normally perform Brownian motion (modelled by the random walks) and which react upon encounter to form some new product molecule [4]. Such elementary reactions form the backbone of all biochemical reaction networks, independent of their complexity and are particularly ideal for a comparison between CA and cP models because of the existence of rigorous analytical results from the theory of random walks in low-dimensions. The biological process indicated above simplifies the biological membrane to a homogeneous quasi-two dimensional environment. In reality it is found that the heterogeneous micro-structure of the membrane significantly hinders the free diffusion of molecules on its surface. In particular it is known that transmembrane proteins (denoted with Bin the above) impose relatively static barriers to the smaller and more mobile molecules (denoted with Ain the above). This is due because transmembrane proteins are anchored to the cytoskeleton of the cell. These obstacles are incorporated in the models considered by us by making some parts of the plane inaccessible to particle motion. Modeling Reaction Kinetics with Conformon P Systems 135 A general CA model which describes both cases above (with and without obstacles to particle motion) has been described in [4]. The algorithm is the follows. Initially, particles of two different kinds Aand Bare uniformly distributed on a two-dimensional lattice with unit spacing and periodic boundary conditions (a torus). Particles Acan move, while particles Bare static. One Aand one Bparticle can react when in the same location of the lattice and produce one particle C. Particles Care static and inert. Some of the tests considered another type of static and inert particle, an obstacle, uniformly distributed in the lattice in the initial configuration. At each time step, a particle of type Aor Bis randomly chosen and either moved or subject to a reaction according to the following: the particle can move from the location in the lattice in which it is to a randomly chosen neighbor location only if the chosen neighbor location does not contain any other particle of the same kind or an obstacle; if instead the chosen neighbor lattice location contains a particle of the other kind (that is, if Ais subject to be moved, then Bis the other kind; if Bis subject to be moved, then Ais the other kind), then the particle can react with the particle of the other kind with probability P. If this occurs both particles A and Bare removed and a Cparticle is placed in the chosen neighbor location, otherwise nothing occurs. It is important to note that the algorithm does not allow more than one particle of any type to be in the same location of the lattice, thus enforcing a hard-sphere molecular repulsion. The above two steps are repeated ntot(t) times, where ntot(t) is the current number of distinct particles on the lattice (excluding obstacles) at time t. After one such sequence the time is incremented by one. The simulations are performed with two different lattice types: square (von Neumann) and triangular neighborhoods. Models of cP systems have been derived by the just described CA model. Particles of type Aand Bhave been modeled with [A, 1] and [B, 1] conformons, respectively. Their eventual interaction (with probability P) creates [B, 2] conformons representing the Cparticles. A lattice location of the CA has been modeled with a (membrane) compartment in the cP model. The presence of obstacles has been modeled with compartments in the lattice having no incoming edge (in this way no conformon could move in these compartments). The simulations have been performed using the cP simulator available from [9] modifying it in a way that interaction rules have priority on passage rules. Moreover, ad hoc programs to create the lattices and to analyze the data have been also used. These programs can be requested to the authors. The cP models and the simulations are such that more than one particle can be at the same time in one compartment. 3 Data Analysis Data produced by the simulations consisted of the number of Aand Bparticles as a function of time. For each set of parameter values, ten independent simulations 136 P. Frisco, R. Grima were run on 300×300 lattices until the time (denoted by T) at which there remained only 1% of the minority particle species (that is, the one whose initial concentration is the smallest, which in our case are particles of type A[4]). The majority species is static, the minority species is mobile and their probability of interaction is P. We run the tests with two different values of P: 1 and 0.1. We consider two cases: presence and absence of obstacles uniformly distributed throughout the lattice so to occupy at most 0.4 of the available lattice locations (denoted by [O]=0.4). The data from these ten copies were then averaged to reduce the inherent noise, yielding an array of values [A(t)],[B(t)], t, t = 0...T . The simulation data for the absence of obstacles case can be directly compared to rigorous theoretical results from the theory of random walks [1]. Here it is shown that in a two-dimensional space where the majority particle species is immobile (B) and minority species is mobile (A) and the reaction probability is 1, then for sufficiently long time runs, the rate of change of the concentrations of mobile particles is described by the effective ordinary differential equation: d[A(t)]/dt ∼ −t−1/2[A(t)][B(t)],(1) where [A(t)] denotes the total number of particles of type Aat time tdivided by the total number of lattice locations defining the two-dimensional space. Thus the most basic test of our cP simulations is to use the data obtained for the case of no obstacles and P= 1 to extract the time exponent in the above equation. The method used to obtain this exponent is the one reported in [4] where it is shown that for general differential equations of the type d[A(t)]/dt ∼ −t−(1−p)[A(t)][B(t)], the exponent pis equal to the gradient of the graph of G=Log[−Log(B0[A(t)]/(A0(B0−A0+ [A(t)])))] versus Log(t). Figure 1, bottom curve, shows the variation of the slope (that is, p) with time for the just indicated cP simulations. It is found that p= 0.6. This implies that the ordinary differential equation satisfied by the cP simulation data is d[A(t)]/dt ∼ −t−0.4[A(t)][B(t)]. This result is fairly close to the rigorous theoretical value given above and also agrees with previous CA simulations giving p= 0.5. Figure 1, above curve, shows the results of the simulations for P= 0.1. No rigorous theory exists for this case, but CA simulations [4] give p∼0.85 whereas with cP simulations we obtain p∼0.92. Hence for the case of no obstacles, for both high and low values of reaction probability P, the results of CA and cP are in good quantitative agreement, though there is a consistent tendency of the exponent for cP to be slightly larger than that of CA. The latter discrepancy could be due to the fact that CA simulations impose the condition that only one particle is allowed at a site whereas cP simulations make no such assumption. The lack of such an assumption would necessarily imply a larger amount of “particle mixing” inside each spatial element of cP simulations which from physical considerations [4] would necessitate the exponent pto be closer to one, as observed. To test this hypothesis we developed a cP model in which at most one particle per compartment is allowed. Figure 2 shows the curve comparing the data obtained by the cP models in which more than one particle and at most one particle per Modeling Reaction Kinetics with Conformon P Systems 137 Fig. 1. Variation of the slope with no obstacles in the cP model compartment is allowed. No discernible differences are observed between the two models. This implies that either the effect occurs only in lower dimensions or the possibility to have more than one particle in the same compartment is not the reason for the small discrepancies between CA and cP simulations. There are no rigorous analytical results for the case in which obstacles are present. Anyhow, it has been traditionally assumed that the dynamics in this case would be captured by an effective ordinary differential equation as (1), but with a time exponent pwhich varies somewhere between 0 and 1. This is often referred to as fractal kinetics [5, 7]. However, in [4] it is shown that this is not the case. It is found from CA simulations that the slope is not constant but varies considerably with time and apparently does not approach a constant value in the limit of long time runs. Our cP simulations also confirm this result (Figure 3), once again showing no evidence of a discrepancy between CA and cP simulations. In the present paper we go one step beyond the work reported in [4] and, for the case in which obstacles are present, we find a new effective ordinary equation which captures the dynamics of the reaction. It can be shown [4] that the solution of an ordinary differential equation of the type d[A(t)]/dt ∼ −k(t)[A(t)][B(t)] for long time runs is of the form: [A(t)] ∝exp·−(B0−A0)Zt 0 k(s)ds¸.(2) 138 P. Frisco, R. Grima Fig. 2. Curves comparing results from cP simulations. Blue and pink curves for Aand Bwhen at most 1 particle per compartment is allowed. Yellow and cyan curves for Aand Bwhen more than one particle per compartment is allowed. The graph shows that the variation of particle concentration with time is independent of the one-particle constraint. It is also known that k(t) = dS/dt where Sis the mean number of distinct lattice locations visited by a particle moving in a random walk [5]. It is found that S∼ tds/2for long time runs in a fractal space of spectral dimension ds. This would imply (for long time runs) the dynamics to follow an effective equation of the form d[A(t)]/dt ∼ −t−(1−ds/2)[A(t)][B(t)] which implies a constant time exponent p. However note that to arrive at this conclusion one implicitly assumes that the long time regime is being observed. Actuality one may only observe the early and intermediate time regimes since the simulation halts after 99% of the particle A has been consumed. Inspired by the theoretical results reported in [4], we surmise that the intermediate time scaling for Swould be of the general form: S∼tαLn(1/Ln(tα)) where the exponent αis introduced to take into account the heterogeneity of space imposed by the presence of obstacles. Interestingly, it is found that the cP data is in good agreement with this conjectured law, see Figure 4. Thus our simulations and data analysis suggest a new kinetic equation for describing bimolecular reactions in obstacle-ridden low dimensional media, namely d[A(t)]/dt ∼ −k(t)[A(t)][B(t)] with k(t) = ∂/∂ttαLn(1/Ln(tα)) instead of the customary k(t) = tα. Modeling Reaction Kinetics with Conformon P Systems 139 Fig. 3. Gvalue for the cP tests with more than one particle per compartment and no obstacles 4 Conclusion In this paper we report a preliminary study aiming to understand what kind of biological processes are better fit to be modeled with CA or with cP. In particular, we focused on the possibility offered by cP to model the presence of more than one particle in a compartment. From the tests we run we conclude that this possibility does not always make a difference in the obtained results. Some differences between the results obtained by similar CA and cP models occurs only if obstacles, locations in the lattice limiting the mobility of the particles, are present. Anyhow, the found differences are not yet sufficient to draw general conclusions. One line of further research is to compare the fluctuations from the average values in CA and cP simulations. Acknowledgements: R. Grima gratefully acknowledges support from SULSA (Scottish Universities Life Sciences Alliance). 242 F. Ipate, M. Gheorghe S S 3 - Left Tree Mutant S + S 1 2 - S S Right Tree Mutant S + S S 3 1 2 + S S S S 3 S + S 1 2 S S 3 rd Level Mutants of the original tree Fig. 4. 3rd level mutants The grammar definition will depend on the level at which testing is intended to be performed. At a high level (for instance in integration testing) the predicates MaxParal and Apply will normally be assumed to be correctly implemented and so they will be presented as terminals in the grammar; obviously, they can be themselves described by context-free grammars and appropriate mutants will be generated in a similar fashion at lower level of testing. On the other hand, it is possible to incorporate the definitions of the two predicates into the definition of the transition relation H; in this case the corresponding grammar will be much more complex and system testing will be performed in one single step. Naturally, Mutation Based Testing of P Systems 243 for complexity reasons, in practice a multi-phase testing strategy is normally preferred. The following (simplified) example illustrates the above strategy for high-level testing of P systems. Example 2. Consider a 1-membrane P-systems with 2 rules r1:u1→v1,r2:u2→ v2. Then the transition of the Kripke structure representation of Πis given by the formulae: •(u, v)∈H,u, v ∈N2 Max, if ∃n1, n2∈N·MaxParal(u, u1, v1, n1, u2, v2, n2)∧ Apply(u, v, u1, v1, n1, u2, c2, n2); •(u, Halt)∈H,u∈N2 Max, if ¬∃v∈N2 Max, n1, n2∈N·Apply(u, v, u1, v1, n1, u2, v2, n2); •(u, Crash)∈Hif ¬∃v∈N2 Max ∪ {Halt} · (u, v)∈H; •(Halt, Halt)∈H; •(Crash, Crash)∈H. Then such a system can be described by a context-free grammar G= (V, T, P, S) where •V={S, S1, S2, U, V, U1, V1, U2, V2}; •Tcontains (bounded) vectors from N2, the additional states Hal and Crash, predicates MaxParal and Apply, the “true” logical value, logical operators, quantifiers and other symbols, i.e., T=N2 Max ∪ {Halt, Crash, MaxParal, Apply, true, ∧, , ∨,¬,∃,∀, n1, n2,·,(,)}; •The production rules are: –p1:S→ ¬S; –p2:S→S∧S; –p3:S→S∨S; –p4:S→true; –p5:S→ ∃n1·S1; –p6:S1→ ∃n2·S2; –p7:S2→S2∧S2; –p8:S2→Apply(U, V, U1, V1, n1, U2, V2, n2); –p9:S2→MaxParal(U, U1, V1, n1, U2, V2, n2); – rules that transform nonterminals U, U1, V1, U2, V2into vectors from N2. Suppose the following rule mutants are defined: •Mutants for p1:S→S; •Mutants for p2:S→S∨S,S→S; •Mutants for p3:S→S∧S,S→S; •Mutants for p4:S→ ¬true; •Mutants for p5:S→ ∀n1·S1; •Mutants for p6:S1→ ∀n2·S2; •Mutants for p7:S1→S∨S1,S1→S1; 244 F. Ipate, M. Gheorghe •Mutants for p8: negate de predicate, change parameters such that the obtained formula is syntactically correct, e.g. switch uand u1; •p9: negate de predicate, change parameters such that the obtained formula is syntactically correct; •remaining rules: change each integer value by adding or removing 1. Now, consider the P system Πwith rules r1:a→ab,r2:a→c. Among the P-system mutants generated using the above procedure are the following: •P systems in which one rules is changed: r1can be replaced by any of λ→ ab (this is an invalid rule and the resulting mutant will have no P system equivalent), aa →ab,ab →ab,ac →ab,a→a,a→b,a→c,a→a2b, a→ab2,a→abc;r2can be substituted in a similar manner. Note that only one rule is mutated at a time. •r1and r2are interchanged (this will result in an equivalent mutant). •A system with rules r1and r2, but which are not applied in a maximal parallel mode (this is obtained by negating the maxParal predicate in the expression of H). •Other erroneous Kripke systems which may have no P system equivalent; these can be obtained, for example, by negating the Apply predicate in the expression of Hor by changing one of its “state” parameters (uor v). Note that in this example we have used a grammar that generates 1-membrane P systems with (at most) two rules and so all generated mutants have this form. More generally, we can use a grammar that describes any 1-membrane P system (with any number of rules). Naturally, in this case the mutant generation process will be much more complex. 5 Conclusions In many applications based on formal specification methods the test sets are generated directly from the formal models. The same applies to formal models based on grammars. However the approach presented in [11], although novel and with many practical consequences, lacks a rigorous method of defining the process of generating the mutants. In this paper a formal method based rigorously defined operations with rules and subtrees of derivation trees is introduced for contextfree grammar formalisms and extended to P systems. Some examples illustrate the approach. Acknowledgment Work supported by the CNCSIS grant IDEI 643/2009 (EvoMT). Mutation Based Testing of P Systems 245 References 1. F. Bernardini, M. Gheorghe, F.J. Romero-Campero, N. Walkinshaw: A hybrid approach to modelling biological systems. Workshop on Membrane Computing 2007, LNCS 4860, 138–159. 2. G. Ciobanu, Gh. P˘aun, M. J. P´erez-Jim´enez, eds.: Applications of Membrane Computing. Springer, 2006. 3. Z. Dang, O.H. Ibarra, C. Li, G. Xie: On the decidability of model-checking for P systems. Journal of Automata, Languages and Combinatorics, 11, 3 (2006), 279–298. 4. M. Gheorghe, F. Ipate: On testing P systems. Workshop on Membrane Computing, 2008, LNCS 5391, 204–216. 5. M. Holcombe, F. Ipate: Correct Systems: Building a Business Process Solution. Springer, 1998. 6. J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley, 2001. 7. F. Ipate, M. Gheorghe: Testing non-determinstic stream X-machine model and P systems. Electronic Notes in Theoretical Computer Science, 227 (2009), 113–126. 8. F. Ipate, M. Gheorghe: Finite state based testing of P systems. Natural Computing, 2009, to appear. 9. J. Offutt: A practical system for mutation testing: Help for the common programmer. International Test Conference, 1994, 824–830. 10. Y.-S. Ma, J. Offutt, Y.R. Kwon: MuJava – An automated class mutation system. Software Testing, Verification and Reliability, 15, 2 (2005), 97–133. 11. J. Offutt, P. Ammann, G. Mason, L. (Ling) Liu: Mutation testing implements grammar-based testing. Proceedings of the Second Workshop on Mutation Analysis, 2006. 12. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 13. Gh. P˘aun: Membrane Computing. An Introduction. Springer, 2002. 14. http://en.wikipedia.org/wiki/Mutation testing 15. http://cs.gmu.edu/ offutt/mujava/ 16. http://ppage.psystems.eu Author Index Alhazov, Artiom, I1, I9, I23 Aman, Bogdan, I29 Ardelean, Ioan I., I41 Barbuti, Roberto, I51 Caravagna, Giulio, I51 Cardona, M´onica, I65, I81 Cecilia, Jose M., II45 Ciencialov´a, Lucie, I97 Ciobanu, Gabriel, I29 Cojocaru, Svetlana, I1 Colomer, M. Angels, I65, I81 Csuhaj-Varj´u, Erzs´ebet, I97 D´ıaz-Pernil, Daniel, I109 Dinneen, Michael J., II85 Frisco, Pierluigi, I123, I133 Gallego-Ortiz, Pilar, I109 Garc´ıa, Jos´e M., II45 Garc´ıa-Quismondo, Manuel, I141 Gheorghe, Marian, I231 Grima, Ramon, I133 Guerrero, Gin´es D., II45 Guti´errez-Escudero, Rosa, I141, I169 Guti´errez-Naranjo, Miguel A., I109, I181, I199, I211 Henley, Beverley M., I227 Ipate, Florentin, I231 Ishdorj, Tseren-Onolt, II1, II235 Kelemenov´a, Alica, I97 Kim, Yun-Bum, II85 248 Krassovitskiy, Alexander, I9, II29 Leporati, Alberto, I181, II1, II213 Maggiolo-Schettini, Andrea, I51 Malahova, Ludmila, I1 Manca, Vincenzo, II115 Margalida, Antoni, I65 Mart´ınez-del-Amor, Miguel A., I199, II45 Mauri, Giancarlo, II213 Milazzo, Paolo, I51 Mingo, Jack Mario, II59 Morita, Kenichi, I23 Murphy, Niall, II73 Nicolescu, Radu, II85 ObtuÃlowicz, Adam, II109 Pagliarini, Roberto, II115 Pan, Linqiang, II1, II127, II139, II151, II169, II235 P˘aun, Gheorghe, II127, II139, II151, II197, II207 P´erez-Hurtado, Ignacio, I65, I141, I199, II45 P´erez-Jim´enez, Mario J., I65, I81, I109, I141, I169, I199, I211, II45, II151, II169 Porreca, Antonio E., II213 Riscos-N´u˜nez, Agust´ın, I109 Rius-Font, Miquel, I169 Rogozhin, Yurii, I1, I9 Sanuy, Delf´ı, I65 Sburlan, Drago¸s, II225 Vaszil, Gy¨orgy, I97 Verlan, Sergey, I9 Wang, Jun, II235 Woods, Damien, II73 Zandron, Claudio, II213 Zeng, Xiangxiang, II1 Zhang, Xingyi, II1