P Systems: from Anti-Matter to Anti-Rules

P Systems: from Anti-Matter to Anti-Rules Artiom Alhazov1, Rudolf Freund2, Sergiu Ivanov3, Mario J. P´erez-Jim´enez4 1Vladimir Andrunachievici Institute of Mathematics and Computer Science Academiei 5, Chi¸sin˘au, MD-2028, Moldova E-mail: [email protected] 2TU Wien, Institut f¨ur Logic and Computation Favoritenstraße 9–11, 1040 Wien, Austria E-mail: [email protected] 3IBISC, Universit´e ´ Evry, Universit´e Paris-Saclay 23, boulevard de France, 91034 ´ Evry, France E-mail: [email protected] 4Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain E-mail: [email protected] Summary. The concept of a matter object being annihilated when meeting its corresponding anti-matter object is taken over for rule labels as objects and anti-rule labels as the corresponding annihilation counterpart in P systems. In the presence of a corresponding anti-rule object, annihilation of a rule object happens before the rule that the rule object represents, can be applied. Applying a rule consumes the corresponding rule object, but may also produce new rule objects as well as anti-rule objects, too. Computational completeness in this setting then can be obtained in a one-membrane P system with non-cooperative rules and rule / anti-rule annihilation rules when using one of the standard maximally parallel derivation modes as well as any of the maximally parallel set derivation modes (i.e., non-extendable (multi)sets of rules, (multi)sets with maximal number of rules, (multi)sets of rules affecting the maximal number of objects). When using the sequential derivation mode, at least the computational power of partially blind register machines is obtained. 1 Introduction The basic model of P systems as introduced in [24] can be considered as a distributed multiset rewriting system, where all objects – if possible – evolve in parallel in the membrane regions and may be communicated through the membranes. Overviews on the field of P systems can be found in the monograph [25] and the handbook of membrane systems [26]; for actual news and results we refer to the 42 A. Alhazov, R. Freund, S. Ivanov, and M.J. P´erez-Jim´enez P systems webpage [28] as well as to the Bulletin of the International Membrane Computing Society. Computational completeness (computing any partial recursive relation on nonnegative integers) can be obtained with using cooperative rules or with catalytic rules (possibly) together with non-cooperative rules. We recall that noncooperative rules have the form a→w, where ais a symbol and wis a multiset, catalytic rules have the form ca →cw, where the symbol cis called the catalyst, and cooperative rules have no restrictions on the form of the left-hand side. Without additional control mechanisms, at least two catalysts are needed, see [16]. Using specific control mechanisms, as for example, rule labels or target agreement, only one catalyst is needed, for example, see [14, 19, 20]. In [2, 1], another concept to avoid cooperative rules is investigated: for any object a(matter), its anti-object (anti-matter) a−is considered together with the corresponding annihilation rule aa−→λ, which is assumed to exist in all membranes; this annihilation rule is assumed to be a special non-cooperative rule having priority over all other rules in the sense of weak priority (e.g., see [9], i.e., other rules then also may be applied if objects cannot be bound by some annihilation rule any more). For spiking neural P systems, the idea of anti-matter has been introduced in [23] with anti-spikes as anti-matter objects. In [12] the power of anti-matter for solving NP-complete problems is exhibited. Although, as expected (for example, compare with the Geffert normal forms, see [27]), the annihilation rules are rather powerful, it is still surprising that using matter/anti-matter annihilation rules as the only non-cooperative rules, with the annihilation rules having weak priority, computational completeness can already be obtained without using any catalyst, see [2, 1], whereas usually at least one catalyst is needed even when using other control mechanisms, for example, see [2]. In this paper we now consider a rule label as an object itself which cannot evolve as any other object in the system, but only has the task to make the rule applicable; in some sense this can be seen as a variant of rule activation as introduced in P systems with activation and blocking of rules, see [4]; for the concept of activation and blocking of rules also see [3, 5]. Introducing the anti-rule object then can be seen as a variant of blocking the corresponding rule. The main difference between these two concepts – activation and blocking of rules in contrast to rule objects and anti-rule objects – is that with activation and blocking of rules, rules can be activated and blocked for specific time steps in the future, whereas the activation of a rule by its rule object is immediate, and also blocking is immediate, but active until the anti-rule object annihilates with the rule object, which may be an unbounded number of steps in the future. When a rule is applied by consuming its corresponding rule object is also not fixed and may heavily depend not only on the applicability of the rule, but also on the derivation mode. For example, in the sequential mode, several rule objects may compete for the rule each of them represents to be executed; the sequence of applications may be crucial, as in between an anti-rule object may appear and annihilate the rule object. Finally, let us mention that the concepts of activation of rules and of rule objects already P Systems: from Anti-Matter to Anti-Rules 43 have appeared in some different way in [13] embedded in an even more complex setting. We also have to emphasize that each copy of a rule object allows for exactly one application of the corresponding rule it represents, i.e., we deal with multisets of rules only applicable if the corresponding multiset of rule objects is present, which restricts the set of applicable sets of multisets of rules in a given derivation mode, especially in the maximally parallel derivation modes. This also means that we have to deal with a subtle technical detail: We either may start with the set of all applicable sets of multisets of rules, no matter which and how many rule objects are present, then take out all the multisets of rules which conform with the given derivation mode, and then only take those for which sufficient resources of rule objects are available. On the other hand, we may also first take only those multisets of rules for which there are sufficient resources of rule objects available, take these as the set of applicable rule multisets and only afterwards apply the condition for the derivation mode. Examples to explain these differences will be given in Section 3. After explaining some notions and definitions used in this paper in the next section, in Section 3 we will define our new model of P systems with rule and anti-rule objects as well the kind of rules, the derivation modes, and the halting conditions used afterwards; moreover, some examples are given to illustrate the new concept. In Section 4, we then establish our main results. We show that computational completeness can even be obtained with one-membrane P systems using non-cooperative rules and rule / anti-rule annihilation rules as well as one of the standard maximally parallel derivation modes or maximally parallel set derivation modes (i.e., non-extendable (multi)sets of rules, (multi)sets with maximal number of rules, (multi)sets of rules affecting the maximal number of objects). When using the sequential derivation mode, at least the computational power of partially blind register machines is obtained. A summary of the results we obtained as well as an outlook to future research topics conclude the paper. 2 Prerequisites The set of integers is denoted by Z, and the set of non-negative integers by N. Given an alphabet V, a finite non-empty set of abstract symbols, the free monoid generated by Vunder the operation of concatenation is denoted by V∗. The elements of V∗are called strings, the empty string is denoted by λ, and V∗\{λ}is denoted by V+. For an arbitrary alphabet V={a1, . . . , an}, the number of occurrences of a symbol aiin a string xis denoted by |x|ai, while the length of a string x is denoted by |x|=Pai∈V|x|ai. The Parikh vector associated with xwith respect to a1, . . . , anis (|x|a1,...,|x|an). The Parikh image of an arbitrary language L over {a1, . . . , an}is the set of all Parikh vectors of strings in L, and is denoted by Ps(L). For a family of languages FL, the family of Parikh images of languages 44 A. Alhazov, R. Freund, S. Ivanov, and M.J. P´erez-Jim´enez in FL is denoted by P sF L, while for families of languages over a one-letter (dletter) alphabet, the corresponding sets of non-negative integers (d-vectors with non-negative components) are denoted by NFL (NdFL ). A (finite) multiset over a (finite) alphabet V={a1, . . . , an}, is a mapping f: V→Nand can be represented by haf(a1) 1, . . . , af(an) nior by any string xfor which (|x|a1,...,|x|an) = (f(a1), . . . , f(an)). In the following we will not distinguish between a vector (m1, . . . , mn), a multiset ham1 1, . . . , amn nior a string x having (|x|a1,...,|x|an)=(m1, . . . , mn). Fixing the sequence of symbols a1, . . . , anin an alphabet Vin advance, the representation of the multiset ham1 1, . . . , amn niby the string am1 1. . . amn nis unique. The set of all finite multisets over an alphabet Vis denoted by V◦. The family of regular and recursively enumerable string languages is denoted by REG and RE, respectively. For more details of formal language theory the reader is referred to the monographs and handbooks in this area as [11] and [27]. Register machines Aregister machine is a tuple M= (m, B, l0, lh, P), where mis the number of registers, Bis a set of labels, l0∈Bis the initial label, lh∈Bis the final label, and Pis the set of instructions bijectively labeled by elements of B. The instructions of Mcan be of the following forms: •l1: (ADD(j), l2, l3), with l1∈B\{lh},l2, l3∈B, 1 ≤j≤m. Increases the value of register jby one, followed by a non-deterministic jump to instruction l2or l3. This instruction is usually called increment. •l1: (SUB(j), l2, l3), with l1∈B\{lh},l2, l3∈B, 1 ≤j≤m. If the value of register jis zero then jump to instruction l3; otherwise, the value of register jis decreased by one, followed by a jump to instruction l2. The two cases of this instruction are usually called zero-test and decrement, respectively. •lh:HALT. Stops the execution of the register machine. Aconfiguration of a register machine is described by the contents of each register and by the value of the current label, which indicates the next instruction to be executed. Computations start by executing the instruction l0of P, and terminate with reaching the HALT-instruction lh. For useful results on the computational power of register machines, we refer to [22]. In partially blind register machines, the SUB instruction has the form p: (SUB(r), q): if the register ris not empty, it is decremented and the register machine moves to state q, otherwise the machine crashes – the computation stops in a non-halting configuration, yielding no result. Moreover, we require that valid computations of a partially blind register machine have 0 in all non-output registers in halting configurations. P Systems: from Anti-Matter to Anti-Rules 45 3 P Systems with Rule and Anti-Rule Objects Formally, a P system with anti-rules (a PARS for short) is a construct Π=V, T, H ∪H−, µ, w1, . . . , wm, R1, . . . , Rm, gH, f, =⇒Π,δwhere •Vis the alphabet of objects; •T⊆Vis the alphabet of terminal objects; •H∪H−is the alphabet of rule objects (H) and anti-rule objects (H−), respectively; we also define VH:= V∪H∪H−; •µis the hierarchical membrane structure (a rooted tree of membranes) with the membranes uniquely labeled by the numbers from 1 to m; •wi∈V∗, 1 ≤i≤m, is the initial multiset in membrane i; •Ri, 1 ≤i≤m, is a finite set of rules of type Xassigned to membrane i; we also define R=S1≤i≤m{(i, r)|r∈Ri}; •gHis a function assigning a rule from Rto every rule object in H; •fis the label of the membrane from which the result of a computation has to be taken from (in the generative case) or into which the initial multiset has to be given in addition to wf(in the accepting case), •=⇒Π,δ is the derivation relation under the derivation mode δ. The symbol Xin “rules of type X” may stand for “cooperative”, “noncooperative”,“purely catalytic”, “catalytic”, etc., see Subsection 3.1. Aconfiguration is a list of the contents of each membrane region; a sequence of configurations C1, . . . , Ckis called a computation in the derivation mode δif Ci=⇒Π,δCi+1 for 1 ≤i<k. The derivation relation =⇒Π,δ is defined by the set of rules in Πand the given derivation mode which determines the multiset of rules to be applied to the multisets contained in each membrane also taking into account the available rule objects, as we will explain in more detail in Subsection 3.4. 3.1 Standard Rule Variants Non-cooperative rules have the form a→w, where ais a symbol and wis a multiset, catalytic rules have the form ca →cw, where the symbol cis called the catalyst, and cooperative rules have no restrictions on the form of the left-hand side. These types of rules will be denoted by ncoo (non-cooperative), pcat (purely catalytic), and coo (cooperative); if both non-cooperative and catalytic rules are allowed, we write cat (catalytic). If in general a P system has more than one membrane, each symbol on the right-hand side may have assigned a target where the symbol has to be sent after the application of the rule, where the targets take into account the tree structure of the membranes as follows: here the symbol stays in the membrane where the rule is applied; out the symbol is sent to the outer membrane, i.e., the membrane enclosing the membrane where the rule is applied; 46 A. Alhazov, R. Freund, S. Ivanov, and M.J. P´erez-Jim´enez in the symbol is sent to an inner membrane, i.e., a membrane enclosed by the membrane where the rule is applied; injthe symbol is sent to the inner membrane labeled by j. 3.2 Derivation Modes In general, the set of all multisets of rules applicable in a P system to a given configuration Cis denoted by Appl(Π, C) and can be restricted by imposing specific conditions, thus yielding the following basic derivation modes (for example, see [21] for formal definitions): •asynchronous mode (abbreviated asyn): at least one rule is applied; •sequential mode (sequ): only one rule is applied; •maximally parallel mode (max): a non-extendable multiset of rules is applied; •maximally parallel mode with maximal number of rules (maxrules): a nonextendable multiset of rules of maximal possible cardinality is applied; •maximally parallel mode with maximal number of objects (maxobjects): a nonextendable multiset of rules affecting as many objects as possible is applied. In [7], these derivation modes are restricted in such a way that each rule can be applied at most once, thus yielding the set modes sasyn,smax,smaxrules, and smaxobjects (the sequential mode is already a set mode by definition): •asynchronous set mode (abbreviated sasyn): at least one rule is applied, but each rule at most once; •maximally parallel set mode (smax): a non-extendable set of rules is applied; •maximally parallel set mode with maximal number of rules (smaxrules): a non-extendable set of rules of maximal possible cardinality is applied; •maximally parallel set mode with maximal number of objects (smaxobjects): a non-extendable set of rules affecting as many objects as possible is applied. Let us denote the set of all multisets (possibly only sets) of rules applicable in a (tissue) P system Πto a given configuration Cin the derivation mode δby Appl(Π, C, δ). We immediately observe that Appl(Π, C, asyn) = Appl(Π, C). To collect the set and multiset derivation modes, we use the following notations: DS={sequ, sasyn, smax, smaxrules, smaxobjects}and DM={asyn, max, maxrules, maxobjects}. 3.3 Halting Conditions Besides the standard total halting with no (multi)set of rules being applicable any more to the current configuration, some more variants of halting conditions have been considered in the literature: total halting (H) the common halting strategy where the computation stops with no (multi)set of rules being applicable any more P Systems: from Anti-Matter to Anti-Rules 47 unconditional halting (u) the result of a computation can be taken from every configuration derived from the initial one (possibly only taking terminal results) partial halting (h) the set of rules Ris partitioned into disjoint subsets R1to Rh, and a computation stops if there is no multiset of rules applicable to the current configuration which contains a rule from every set Rj, 1 ≤j≤h halting with states (s) the configuration with which a derivation may stop must fulfill a recursive condition (which corresponds with a final state) The variant of unconditional halting was introduced in [10]. Partial halting, for example, was investigated in [6, 8, 18], using the membranes for partitioning the rules. Formal definitions for the halting conditions H, h, s can be found in [21]. In the description for P systems, the derivation relation under the derivation mode δ, =⇒Π,δ, is extended by the halting condition, i.e., we then write =⇒Π,δ,β for β∈ {H, h, u, s}. By default, βis understood to be the total halting Hand then usually omitted. 3.4 Rule and Anti-Rule Objects In the set of rules R, the rules on the left-hand side may only contain symbols from V, whereas on the right-hand side of a rules any symbol from VHmay appear. In any computation step of a PARS Πonly a multiset R0of rules can be applied such that for each (copy of a) rule ra rule object hwith g(h) = ris present in the current configuration. With the application of a rule r, a copy of a rule object h with g(h) = ris consumed, i.e., the number of rule objects in the sense of multisets is important for the applicability of a multiset of rules. As we allow anti-rule objects to be generated, too, we implicitly assume the rule / anti-rule annihilation rule hh−→λto be present in every membrane, for every h∈H. Before the next derivation step as described above can be carried out, all such annihilation rules have to be executed, as we assume them to have (weak) priority over all other rules. As already mentioned in Section 1, each copy of a rule object allows for exactly one application of the corresponding rule it represents, i.e., we deal with multisets of rules only applicable if the corresponding multiset of rule objects is present, which restricts the set of applicable sets of multisets of rules in a given derivation mode, especially in the maximally parallel derivation modes. Hence, there are two possible ways how to define the applicable multisets of rules applicable to a given configuration; we observe that a configuration may contain elements from VH, not only V, but as the rule / anti-rule annihilation rules hh−→λhave weak priority, no pair hh−can be present any more: starting with applicable multisets (δa) We start with the set of all applicable sets of multisets of rules, no matter which and how many rule objects are present, then take out all the multisets of rules which conform with the given derivation 48 A. Alhazov, R. Freund, S. Ivanov, and M.J. P´erez-Jim´enez mode, and then only take those for which sufficient resources of rule objects are available. starting with available rule objects (δr) We first take only those multisets of rules for which there are sufficient resources of rule objects available, take these as the set of applicable rule multisets and only afterwards apply the condition for the derivation mode. Which variant we choose for a given derivation mode, will be indicated by a subscript aor rto δ, i.e., we write δaand δr, respectively. The language generated by the PARS Πis the set of all terminal multisets which can be obtained in the output membrane fstarting from the initial configuration C1= (w1, . . . , wm) using the derivation mode δα,α∈ {a, r}, in a halting computation using the halting condition β, i.e., Lgen,δα,β (Π) = nC(f)∈T◦|C1 ∗ =⇒Π,δα,β C∧haltingδα,β(C)o, where C(f) stands for the multiset contained in the output membrane fof the final configuration Cand haltingδα,β (C) indicates that Cis a halting configuration with respect to the halting condition βwhen using δα. The family of languages of multisets generated by PARSs of type Xwith at most nmembranes in the derivation mode δαusing the halting condition βis denoted by P sgen,δα,βOPn(X). We may also consider PARSs as accepting mechanisms: in membrane f, we add the input multiset w0to wfin the initial configuration C1= (w1, . . . , wm) thus obtaining C1[w0]=(w1, . . . , wfw0, . . . , wm); the input multiset w0is accepted if there exists a halting computation in the derivation mode δαstarting from C1[w0], i.e., Lacc,δα,β (Π) = nw0∈T◦| ∃C:C1[w0]∗ =⇒Π,δα,β C∧haltingδα,β(C)o. Then the family of languages of multisets accepted by PARSs of type Xwith at most nmembranes in the derivation mode δαusing the halting condition βis denoted by P sacc,δα,βOPn(X). We finally mention that PARSs can also be used to compute functions and relations, with using fboth as input and output membrane or even using two different membranes for the input and the output. Yet in this paper we will mainly focus on the generating case. 3.5 Flattening As many variants of P systems can be flattened to only one membrane, see [17], we often may assume the simplest membrane structure of only one membrane which in effect reduces the P system to a multiset processing mechanism, and, observing that f= 1, in what follows we then will use the reduced notation P Systems: from Anti-Matter to Anti-Rules 49 Π=V, T, H ∪H−, w, R, gH,=⇒Π,δα,β for a PARS with only one membrane, for which the definitions for the language generated by Πand the language accepted by Πcan be written in an easier way, i.e., Lgen,δα,β (Π) = nv∈T◦|w∗ =⇒Π,δα,β v∧haltingδα,β(v)oand Lacc,δα,β (Π) = nw0∈T◦| ∃v:ww0 ∗ =⇒Π,δα,β v∧haltingδα,β(v)o. The family of languages of multisets generated by one-membrane PARSs of type Xin the derivation mode δαusing the halting condition βis denoted by Psgen,δα,βOP (X). The family of languages of multisets accepted by one-membrane PARSs of type Xin the derivation mode δαusing the halting condition βis denoted by Psacc,δα,βOP (X). The following example illustrates that the two variants δaand δaneed not yield the same results: Example 1. Take the PARS Π=V={a}, T ={a}, H ∪H−, w =ar, R ={a→aar}, gH,=⇒Π,δα,u with H={r}and gH={(r, a →aar)}. Then, with every application of the rule r:a→aar we get one more symbol a, i.e., for α∈ {a, r}, we have {a}+=Lgen,sequα,u (Π) = Lgen,smaxα,u (Π) =Lgen,maxr,u (Π). But on the other hand, Lgen,maxa,u (Π) = {a, aa}, because after the first application of rule rwe obtain the configuration aar, which is a terminal one, as the only applicable multiset of rules which is not extendable would contain two copies of the rule a→aar, yet only one corresponding rule object ris available. The following example shows that different results are obtained with different derivation modes δ: Example 2. Take the PARS Π=V={a}, T ={a}, H ∪H−, w =ar, R ={a→aarr}, gH,=⇒Π,δα,u with H={r}and gH={(r, a →aarr)}. Then, with every application of the rule r:a→aarr we double the number of symbols awhen using a maximally parallel derivation mode, i.e., for α∈ {a, r}, we have Lgen,δα,u (Π) = na2n|n≥0o 56 A. Alhazov, R. Freund, S. Ivanov, and M.J. P´erez-Jim´enez anti-rule objects. A rule object decaying in ttime steps means that it can only activate the application of the rule it stands for during the next tderivation steps, whereafter the rule object vanishes even without the application of the rule / antirule annihilation rule. Acknowledgements The ideas for this paper came up in the inspiring atmosphere of the Brainstorming Week on Membrane Computing in Sevilla this year. References 1. Alhazov, A., Aman, B., Freund, R.: P systems with anti-matter. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Sos´ık, P., Zandron, C. (eds.) Membrane Computing – 15th International Conference, CMC 2014, Prague, Czech Republic, August 20–22, 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8961, pp. 66–85. Springer (2014). https://doi.org/10.1007/978-3-319-14370-5 5 2. Alhazov, A., Aman, B., Freund, R., P˘aun, Gh.: Matter and anti-matter in membrane systems. In: Mac´ıas-Ramos, L.F., Mart´ınez-del-Amor, M.A., P˘aun, Gh., Riscos-N´u˜nez, A., Valencia-Cabrera, L. (eds.) Proceedings of the Twelfth Brainstorming Week on Membrane Computing. pp. 1–26 (2014), http://www.gcn.us.es/files/12bwmc/001 bwmc2014AntiMatter.pdf 3. Alhazov, A., Freund, R., Ivanov, S.: Introducing the concept of activation and blocking of rules in the general framework for regulated rewriting in sequential grammars. In: Proceedings of BWMC 2018 (2018) 4. Alhazov, A., Freund, R., Ivanov, S.: P systems with activation and blocking of rules. In: Stepney, S., Verlan, S. (eds.) Unconventional Computation and Natural Computation – 17th International Conference, UCNC 2018, Fontainebleau, France, June 25-29, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10867, pp. 1–15. Springer (2018). https://doi.org/10.1007/978-3-319-92435-9 1 5. Alhazov, A., Freund, R., Ivanov, S.: Sequential grammars with activation and blocking of rules. In: Machines, Computations, and Universality – 8th International Conference, MCU 2018, Fontainebleau, France, June 28-30, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10881, pp. 51–68 (2018). https://doi.org/10.1007/978-3-319-92402-1 3 6. Alhazov, A., Freund, R., Oswald, M., Verlan, S.: Partial halting in P systems using membrane rules with permitting contexts. In: Durand-Lose, J., Margenstern, M. (eds.) Machines, Computations, and Universality. pp. 110–121. Springer, Berlin, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74593-8 10 7. Alhazov, A., Freund, R., Verlan, S.: P systems working in maximal variants of the set derivation mode. In: Leporati, A., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) Membrane Computing – 17th International Conference, CMC 2016, Milan, Italy, July 25-29, 2016, Revised Selected Papers. Lecture Notes in Computer Science, vol. 10105, pp. 83–102. Springer (2017). https://doi.org/10.1007/978-3-319-54072-6 6 8. Alhazov, A., Oswald, M., Freund, R., Verlan, S.: Partial halting and minimal parallelism based on arbitrary rule partitions. Fundam. Inform. 91(1), 17–34 (2009). https://doi.org/10.3233/FI-2009-0031 P Systems: from Anti-Matter to Anti-Rules 57 9. Alhazov, A., Sburlan, D.: Static sorting P systems. In: Ciobanu, G., P´erez-Jim´enez, M.J., P˘aun, Gh. (eds.) Applications of Membrane Computing, pp. 215–252. Natural Computing Series, Springer (2006). https://doi.org/10.1007/3-540-29937-8 8 10. Beyreder, M., Freund, R.: Membrane systems using noncooperative rules with unconditional halting. In: Corne, D.W., Frisco, P., P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing. pp. 129–136. Springer, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-540-95885-7 10 11. Dassow, J., P˘aun, Gh.: Regulated Rewriting in Formal Language Theory. Springer (1989), https://www.springer.com/de/book/9783642749346 12. D´ıaz-Pernil, D., Pe˜na-Cantillana, F., Alhazov, A., Freund, R., Guti´errez-Naranjo, M.A.: Antimatter as a frontier of tractability in membrane computing. Fundam. Inform. 134(1–2), 83–96 (2014). https://doi.org/10.3233/FI-2014-1092 13. Freund, R.: Generalized P-Systems. In: Ciobanu, G., P˘aun, Gh. (eds.) Fundamentals of Computation Theory, 12th International Symposium, FCT ’99, Ia¸si, Romania, August 30 – September 3, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1684, pp. 281–292. Springer (1999) 14. Freund, R.: Purely catalytic P systems: Two catalysts can be sufficient for computational completeness. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Yu. (eds.) CMC14 Proceedings – The 14th International Conference on Membrane Computing, Chi¸sin˘au, August 20–23, 2013. pp. 153–166. Institute of Mathematics and Computer Science, Academy of Sciences of Moldova (2013), http://www.math.md/cmc14/CMC14 Proceedings.pdf 15. Freund, R.: (Tissue) P systems with decaying objects. In: Csuhaj-Varj´u, E., Gheorghe, M., Rozenberg, G., Salomaa, A., Vaszil, G. (eds.) Membrane Computing – 13th International Conference, CMC 2012, Budapest, Hungary, August 28–31, 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7762, pp. 1–25. Springer (2013) 16. Freund, R., Kari, L., Oswald, M., Sos´ık, P.: Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science 330(2), 251–266 (2005). https://doi.org/10.1016/j.tcs.2004.06.029 17. Freund, R., Leporati, A., Mauri, G., Porreca, A.E., Verlan, S., Zandron, C.: Flattening in (tissue) P systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Yu., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, Lecture Notes in Computer Science, vol. 8340, pp. 173–188. Springer (2014). https://doi.org/10.1007/978-3-642- 54239-8 13 18. Freund, R., Oswald, M.: Partial halting in P systems. Int. J. Found. Comput. Sci. 18(6), 1215–1225 (2007). https://doi.org/10.1142/S0129054107005261 19. Freund, R., Oswald, M.: Catalytic and purely catalytic P automata: control mechanisms for obtaining computational completeness. In: Bensch, S., Drewes, F., Freund, R., Otto, F. (eds.) Fifth Workshop on Non-Classical Models for Automata and Applications – NCMA 2013, Ume˚a, Sweden, August 13 – August 14, 2013, Proceedings. [email protected], vol. 294, pp. 133–150. ¨ Osterreichische Computer Gesellschaft (2013) 20. Freund, R., P˘aun, Gh.: How to obtain computational completeness in P systems with one catalyst. In: Neary, T., Cook, M. (eds.) Proceedings Machines, Computations and Universality 2013, MCU 2013, Z¨urich, Switzerland, September 9–11, 2013. EPTCS, vol. 128, pp. 47–61 (2013). https://doi.org/10.4204/EPTCS.128.13 21. Freund, R., Verlan, S.: A formal framework for static (tissue) P systems. In: Eleftherakis, G., Kefalas, P., P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane 58 A. Alhazov, R. Freund, S. Ivanov, and M.J. P´erez-Jim´enez Computing, Lecture Notes in Computer Science, vol. 4860, pp. 271–284. Springer (2007). https://doi.org/10.1007/978-3-540-77312-2 17 22. Minsky, M.L.: Computation. Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ (1967) 23. Pan, L., P˘aun, Gh.: Spiking neural P systems with anti-matter. International Journal of Computers, Communications & Control 4(3), 273–282 (2009). https://doi.org/10.15837/ijccc.2009.3.2435, http://univagora.ro/jour/index.php/ijccc/article/download/2435/901 24. P˘aun, Gh.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000). https://doi.org/10.1006/jcss.1999.1693 25. P˘aun, Gh.: Membrane Computing: An Introduction. Springer (2002). https://doi.org/10.1007/978-3-642-56196-2 26. P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press (2010) 27. Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer (1997). https://doi.org/10.1007/978-3-642-59136-5 28. The P Systems Website. http://ppage.psystems.eu/