Open Problems, Research Topics, Recent Results on Numerical and Spiking Neural P Systems (The "Curtea de Arge s 2015 Series")

Open Problems, Research Topics, Recent Results on Numerical and Spiking Neural P Systems (The “Curtea de Arge¸s 2015 Series”) Gheorghe P˘aun1, Tingfang Wu2, Zhiqiang Zhang2 1Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania [email protected] 2Key Laboratory of Image Information Processing and Intelligent Control School of Automation, Huazhong University of Science and Technology Wuhan 430074, Hubei, China [email protected], [email protected] Summary. A series of open problems and research topics are formulated, about numerical and spiking neural P systems, initially prepared as a working material for a three months research stage of the second and the third co-author in Curtea de Arge¸s, Romania, in the fall of 2015. Further problems were added during this period, while certain problems were addressed in this time; some details and references are provided for such cases. 1 Introduction In membrane computing there are numerous open problems and research topics in circulation, many of them also collected in systematic lists, compiled, for instance, for the yearly Brainstorming Week on Membrane Computing, see http://ppage.psystems.eu and www.gcn.us.es. Because the present list had initially a working material character, we do not provide here complete references. Furthermore, as the reader is supposed to be a researcher in membrane computing, we do not give basic definitions either (but we give details for the new classes of P systems considered). As a general reference we refer to the Handbook [8]. The list deals only with numerical P systems (in short, NP systems, [7]) and spiking neural P systems (in short, SNP systems, [3]). Some problems are more specific, many others are just general ideas, so that the first step in approaching them implies a formal definition (possibly, of new classes of NP or SNP systems). We recall some details from several papers written in Curtea de Arge¸s during the mentioned period of time. 286 Gh. P˘aun, T. Wu, Z. Zhang 2 Bridging NP and SNP The two “exotic” classes of P systems (their “biochemistry” is not very closely related to the biological one) have many common and, also, many different characteristics. Of the first type is the fact that both of them process numbers and a specific “production” of a cell is distributed among neighboring cells. Thus, it is just natural to check whether features of one class can be extended to the other class, and conversely. This proves to be a very fruitful idea. Here are a few more precise suggestions of this kind. A. NP with SNP features. Three main ingredients of SNP systems can be exported also to NP systems: the tissue-like arrangement of membranes, the regular expressions which control the application of spiking rules, and the replication of the production to all the adjacent cells. However, further features can be considered – only a few suggested below, so this is already a general research issue. B. Passing from the cell-like membrane structure of usual NP systems to tissuelike NP systems is just an extension which will also extend all computing power results and computational complexity properties. As the distribution of the production of a compartment is done with a precise identification of the target variables, a simple (real-time?) mutual simulation between cell-like and tissue-like NP systems is expected. C. What about using, in the tissue-like NP systems, weights on “synapses” instead of repartition coefficients? The simulation of NP systems with weights by systems with repartition coefficients and conversely is a natural research topic. What about using both repartition coefficients and weights on “synapses”? (This might also have economic interpretations, thus bringing the model closer to the initial motivation, the economics.) D. Associating a regular expression with each evolution program seems to be a non-trivial extension of the enzymatic control from [6]. (Note that we can compare the values of two variables, even in terms of regular expressions, in the following way: (x1x2)∗x∗ 2can be interpreted as x2(t)≥x1(t), meaning that the value of x2 at time tis greater than or equal to the value of x1at time t.) In what cases can this intuition be confirmed? A good candidate is the descriptional complexity of various NP systems, for instance, constructed for controlling robots. E. While considering a regular expression looks like adding computing power, distributing the production of a cell to all neighboring variables, replicated, on the one hand, increases the total values of variables in the system, on the other hand, removes the control possibilities provided by the repartition coefficients. Which is the power (and the efficiency) of NP systems with such a repartition protocol remains to be checked. F. Directly related to the previous idea is the following problem: what about NP systems with an “egalitarian” repartition, i.e., with all distribution coefficients equal in each evolution program/in each compartment/in the whole system? A Open Problems on Numerical and SN P Systems 287 particular case is that of considering all distribution coefficients equal to 1. Are such restricted NP systems still universal? G. Continuing with the restrictions, what about considering NP systems with only k≥1 variables in the distribution protocols? Is any difference in power between NP systems with kvariables and those with k+ 1 variables, for various values of k? (It is expected that k= 1 is, indeed, a special case.) What about NP systems with both egalitarian distribution and at most kvariables in each distribution protocol? H. SNP with NP features. This is the “reverse” of problem A, again with (at least) three basic directions: considering SNP systems with a cell-like membrane structure, using a production function instead of spiking rules, and considering a distribution protocol for communicating the produced spikes. What else, it remains to imagine. I. SNP systems with a cell-like membrane structure look “non-natural” from a biological point of view, but it is mathematically interesting, especially in view of the children-parent membrane interaction; remember that circularity is not allowed in standard SNP systems. This idea was explored in [14]; we recall some details. Acell-like SN P system (in short, a cSN P system), of degree m≥1, is a construct Π= (O, µ, n1, . . . , nm, R1, . . . , Rm, io), where O={a},µis a hierarchical membrane structure with mmembranes, ni,1≤ i≤m, is the number of spikes present in compartment iof µat the beginning of the computation, Ri,1≤i≤m, is the finite set of rules from compartment i, and ioindicates the output region (this is the environment if io=env). Besides forgetting rules of the form as→λ, s ≥1,the sets Ricontain spiking rules of the (extended) form E/ac→u, where Eis a regular expression over O, c≥1, and uis a sequence of couples of the form (ap, tar), where p≥1 and tar is a target indication specifying the destination of the passociated spikes. This target can be here, out, in,inj, where jis the label of a membrane, with the usual meaning in cell-like P systems, or inall, with the meaning that the pspikes will be sent, replicated, to all immediately inner membranes (each of them will receive pspikes). Of course, in the case of non-extended rules, when only one spike is produced by a rule, only one couple of the form (a, tar) will be used. The computations in a cSN P system are defined as in usual SN P systems: (at most) one rule in each compartment is applied, but the compartments work in parallel, synchronously. The result can be obtained as the number of the spikes in region ioin the moment when the computation halts, and this can be inside the system or outside, when io=env. We denote by Nin(Π) the set of numbers computed (generated) by the system Πin the internal mode. We will not consider here also the external output in the form of the number of spikes sent out, as this is a direct dual of the inner mode, but, like in SN P systems, we also consider as the result of a computation the distance in time between the first two steps when 288 Gh. P˘aun, T. Wu, Z. Zhang the system sends spikes out; this can be done by rules introducing couples (ap, out) used in the skin region of Π, hence in this case the indication of iois omitted. We denote by N2(Π) the set of numbers computed by Πin this sense, by means of halting or non-halting computations. (By convention, number 0 is computed by a computation which sends out spikes only once.) It is important to note that in the previous definition we have imposed no restriction on the number of produced spikes, that is, it can be greater than the number of consumed spikes. Actually, we need rules for producing more spikes than consumed, otherwise we cannot increase the number of spikes in the system – unless if we use the replication target command inall. We denote by NαcSNPm(forg, here, int, inall), α ∈ {2, in},the family of sets of numbers Nα(Π) computed by cSN P systems Πwith at most mmembranes, using forgetting rules and target indications of the types here, int, inall, together with indications in, out. We explicitly write only forg and the indications here, int, inall because these features are powerful and they can be avoided in certain cases (this also happens in standard SN P systems with forg). When all spiking rules E/ac→uhave cgreater than or equal to the number of spikes in uwe write NαcSN0Pm(...) instead of NαcSNPm(...). When the number of membranes is not bounded, we replace the subscript mwith ∗. Here are the results reported in [14]: 1. NincSNP4(here, int) = NRE. 2. NincSNP7(int) = NRE. 3. NincSNP7=NRE. 4. NincSN0P∗(int, inall) = NRE. 5. N2cSNP4(here, int) = NRE. 6. N2cSN0P∗(here, int, inall) = NRE. Several open problems and research topics were formulated in [14]. First, a large research area is open just by checking whether the results obtained for usual SN P systems can be extended to cSN P systems. Many questions are of interest: looking for small (as the number of membranes) universal cSN P systems, adding anti-spikes, working in a parallel way also in the membranes, working asynchronously, and so on and so forth. In [14] one starts directly with extended systems (without delay). Which is the power of non-extended cSN P systems? In this case we need a way to replicate spikes. In [14] inall it is used to that aim; what else can be imagined? Look for restrictions which lead to characterizations of sub-universal families of numbers (such as NREG) or of languages (in the case of the external output; note that the spike train can be also a sequence of symbols over an arbitrary alphabet). The languages generated by cell-like SN P systems were investigated in [13] – many results were obtained, but also many questions remain to be further examined. We do not enter into details. J. Replacing the spiking rules with a production function (of one variable if only spikes are considered, of two variables if also anti-spikes are used; the interplay Open Problems on Numerical and SN P Systems 289 with the annihilation rule is also of interest – useful seems to be to apply the annihilation rule after computing the production, of both spikes and anti-spikes). The production function can be a polynomial, as in usual NP systems, but we can try to capture also other neural ingredients, such as the sigmoid function on which the functioning of the biological neuron is based. K. Using a distribution protocol, for SNP systems with “standard” spiking rules looks easy: just associate distribution coefficients to synapses. This add “programming” possibilities, hence simpler proofs than for usual SNP systems are expected. 3 Further Problems for NP The investigations on NP systems reported so far only deal with the basic systems and with the enzymatic ones, but there are many possibilities for considering further classes. Some ideas were mentioned also before, a few others will be suggested below, but the reader can imagine many more. L. For instance, we can consider NP systems with restricted communication, in the sense that the production of a compartment is distributed only to variables from one or two levels out of the three used so far: here, down, up. For “one-way” systems it is expected to obtain rather restricted families of numbers generated in this way. Which cases still lead to universality? M. A very natural idea is, instead of having the variables associated with compartments, to move variables across variables by associating with them the usual target indications here, in, out. Numerical P systems with migrating variables (in short, MNP systems) were considered in [17] in the following form: Π= (m, H, µ, V ar, (Pr1, V ar1(0)),...,(Prm, V arm(0)),(xi0, j0)), where: •m≥1 is the number of membranes; •His an alphabet (of labels for membranes in µ); •µis a hierarchical (cell-like) membrane structure with mmembranes labeled with the elements of H; •V ar ={x1, x2, . . . , xn}is a set of variables for the system; •V ari⊂V ar, 1≤i≤m, is a set of variables from V ar, initially present in region i; •V ari(0), 1 ≤i≤m, is a vector which indicates the values of the initial variables in region i; •Pri, 1 ≤i≤m, is the finite set of programs in region i; each program has the following form: 290 Gh. P˘aun, T. Wu, Z. Zhang Fj,i(xp1, . . . , xpk)→cj,1|(xr1, tar1) + . . . +cj,q|(xrq, tarq), where Fj,i(xp1, . . . , xpk) is the production function, cj,1|(xr1, tar1) + . . . + cj,q|(xrq, tarq) is the repartition protocol of the program and tar1, . . . , tarq∈ {here, out, in}; the symbols here, out, in are called target commands or target indications; all the variables xp1, . . . , xpkand xr1, . . . , xrqare from V ar. •xi0∈V ar,j0∈H. The variables initially placed in membrane ihave non-zero values specified by V ari(0),1≤i≤m. A variable equal to zero is simply supposed not to be present in a membrane. This is called the NZP assumption. A program Fj,i(xp1, . . . , xpk)→cj,1|(xr1, tar1)+. . .+cj,q|(xrq, tarq) can be applied only when all variables xp1, . . . , xpk(“production variables”) are present in membrane iat that time with non-zero values. By using the production function, the system computes a production value which is distributed to variables specified by the repartition protocol. An important observation is that variables involved in the production function are reset to zero after computing the production value. The application of programs is as usual in numerical P systems, with the following specific points. After the application of the program, the variables involved in the repartition protocol are moved to the region indicated by the target command associated with them. Specifically, here means the variable will be placed in the same region iwhere the program is applied; out means the variable will be moved to the region immediately outside membrane i– this region can be the environment in the case when iis the skin membrane; in means the variable should be moved to a membrane immediately inside membrane i, non-deterministically chosen. When a program is applied, for a variable involved in the program there are five cases to consider: i) if the variable appears in the production (it must be present in the membrane for the program to be applied) and not also in the repartition protocol, then this variable is zeroed and removed from the membrane; ii) if the variable appears both in the production function (with a non-zero value) and in the repartition, then it is first zeroed, then the variable with the contribution received from the repartition protocol is moved to the membrane indicated by the associated target; iii) if the variable appears in the repartition protocol and is not present in the membrane (hence it must not appear in the production function), then the variable with its contribution received from the repartition protocol is moved to the membrane as the associated target indicates; iv) if the variable appears in the repartition protocol and it was initially present in the membrane but not in the production, then the initial value plus the contribution it receives is moved to the membrane indicated by its associated target; v) if the variable appears in several repartition protocols, then, in order to avoid any conflicts/complications, we restrict to applying programs where the same variable has associated the same target indication in all programs; then, each program separately changes the variable as stated above and the variable, with the summed value, is moved to the associated target. Open Problems on Numerical and SN P Systems 291 After moving variables to the target membranes, all the values of the same variable received from different membranes are added up, and the sum is the value of this variable in the destination membrane. If the sum is zero, then the variable is simply removed from the membrane. (Another possibility is to immediately move variables with the value received from each program to the associated targets and to sum the values at the destination.) MNP systems can evolve in the all-parallel mode (at each step, in each membrane, all programs which can be applied are applied, allowing that several programs share the same variable), in the sequential mode (at each step, only one program is applied in each membrane; if more than one program in a membrane can be used, then one of them is non-deterministically chosen), or in the oneparallel mode (apply programs in the all-parallel mode with the restriction that one variable can appear in only one of the applied programs; in the case of multiple choices, the programs to apply are chosen in the non-deterministic way). In the one-parallel mode, where more than one program can be applied in a membrane, one can also impose the restriction that there is no conflict between the targets associated with variables in the repartition protocols of the applied programs. Besides programs as above (called non-enzymatic), numerical P systems also have enzymatic programs of the form Fj,i(xp1, . . . , xpk)|ej,i →cj,1|(xr1, tar1)+. . .+ cj,q|(xrq, tarq),where ej,i is a variable present in membrane iand different from xp1, . . . , xpkand xr1, . . . , xrq. Such a program is applied at time tonly if ej,i(t)> min(xp1(t), . . . , xpk(t)). Note that ej,i(t) remains unchanged in the program where it appears as an enzymatic variable; in other programs, ej,i can appear as a usual variable in production functions or repartition protocols, and it can be “consumed” or receive “contributions”. If every program is enzymatic, we call the system purely enzymatic. Using the programs in the way mentioned above, we obtain transitions among configurations. A sequence of such transitions forms a computation. If no program can be applied in the current configuration, we say that the system halts. When the system halts, the value taken by the special variable xi0in membrane j0is the number generated by the computation. The set of natural numbers generated by a system Πworking in the one-parallel or sequential mode is denoted by Nα(Π), α ∈ {one, seq},where one stands for oneparallel, seq stands for sequential. We use NαM0βNP D m(polyn(r), V ark1, Prok2), to denote the family of all sets Nα(Π), α∈ {one, seq},β∈ {E, pE, −} of numbers generated by βnumerical P systems Πwith migrating variables (E= enzymatic, pE = purely enzymatic; if the system is non-enzymatic, then βis omitted), with at most mmembranes, at most k1variables, and at most k2programs, with production functions which are polynomials of degree at most n, with integer coefficients, with at most rvariables in each polynomial; Dindicates the use of deterministic systems (we remove it when the systems may also be non-deterministic); the superscript 0 means the system works under the NZP assumption. If this assumption is removed, hence the variables can be present also with value zero, and the programs can be applied if the variables are present in the membrane, does not 292 Gh. P˘aun, T. Wu, Z. Zhang matter whether or not their values are zero (we say that we work without the NZP assumption), then the superscript 0 is removed. If one of the parameters m, n, r, k1, k2is not bounded, then we replace it with ∗. Here are part of the results proved in [17]: 1. NαM0NP1(poly1(1), V ar2, Pro2)−SLIN+ 16=∅, α ∈ {one, seq}. 2. SLIN+ 1⊂NαM0NP1(poly1(1), V ar∗, Pro∗), α ∈ {one, seq}. 3. NoneM0NP1(poly1(3), V ar∗, Pro∗) = NRE. 4. NseqM0NP2(poly1(3), V ar∗, Pro∗) = NRE. 5. NoneMENP1(poly1(3), V ar∗, Pro∗) = NRE. 6. NseqMENP2(poly1(3), V ar∗, Pro∗) = NRE. Also the possibility to generate strings with these systems was explored in [17]. N. Associate a language to a computation in an NP system. For instance, the values of a variable can form a string – in general, over an infinite alphabet (like in [2]), or on a finite alphabet. For instance, we can consider the binary string obtained by marking with 0 and 1 the odd and the even values of the distinguished variable. We can also “read” the natural numbers modulo a given constant k≥2, so that we can obtain strings over an alphabet with kletters. O. In particular, we can associate a language to an NP system by considering an external output: we add a variable also to the environment, which gets parts of the production of the skin compartment. This can be used both for computing numbers and strings (in the latter case, following the suggestions from the previous question). NP systems used as string generators were considered in [16]. A string is associated with a computation in a way somewhat similar to that adopted for spiking neural P systems: one just considers a special variable out in the environment which can appear in the repartition protocol of programs in the skin region of a numerical P system. At each step its value is first reset to zero, then it receives a new value. If at one step it receives several values from several programs, all these values are added up and the sum is the value it receives at this step. If the value is a number ibetween 1 to q, for some constant q, then the symbol biis added to the generated string. If at any step variable out receives a value which is greater than qor smaller than 0, then this computation aborts, no result is associated with it. In order to define the generated string, we need to define its end. This is clear in the case when the computation halts (no further program can be applied), and this can be taken as a definition of successful computations in purely enzymatic P systems. In non-enzymatic and in (non-purely) enzymatic systems the computations never halt, and then we define the end of the string by means of a signal, e.g., the step when the system sends out value 0. Because for purely enzymatic systems we have halting at our disposal, in this case we avoid sending out value 0, that is, this case is simply ignored. (For a general definition, however, a decision should be made also for value 0 sent out. A possibility is to proceed as in spiking neural P systems, where in such a case a special symbol, b0, is added to the string.) Open Problems on Numerical and SN P Systems 293 It still remains a case not covered: the steps when the system sends no value to variable out. We have two choices: to forbid such steps, by the definition of correct computations, or to proceed as in the case of spiking neural P systems and to associate the string λto the generated string (the string is not increased, the system can continue working). In this way, we define two languages generated by a numerical P system Π. If at each step a positive value is sent to variable out (with the exception of the last step, for non-enzymatic and for enzymatic P systems, when value 0 is sent out, marking the end), then we denote the generated language by Lres(Π) (with res coming from restricted). If in the steps when no value is sent out (neither 0) we interpret that the system adds λto the generated string, then the generated language is denoted by Lλ(Π). For an easier remembering, we synthesize the previous conventions/definitions in a table: Sending out Non-enzymatic & Enzymatic Purely enzymatic 1,2, . . . , q bibi <0 or > q abort abort 0 end signal ignored here nothing λor forbidden (res)λor forbidden (res) We denote by LαβNP γ m(polyn(r), V ark1, Prok2), α∈ {res, λ},β∈ {E, pE, −}, γ∈ {hal, fin}, the family of languages Lα(Π), generated by βnumerical P systems Π(E= enzymatic, pE = purely enzymatic; if the system is non-enzymatic, then βis omitted) with at most mmembranes, at most k1variables, and at most k2programs, with production functions which are polynomials of degree at most n, with integer coefficients, with at most rvariables in each polynomial; the superscript γ=hal is used for purely enzymatic systems, to indicate that the result is obtained when the system reaches a halting configuration; in the case when the end of the computation is defined by means of a signal (sending value 0 out), then we replace hal by fin. If one of the parameters m, n, r, k1, k2is not bounded, then we replace it with ∗. Here are some of the results proved in [16]: 1. LresβNPγ ∗(poly ∗n(∗), V ar∗, Pro∗)⊆REC,β∈ {E, pE, −},γ∈ {hal, fin}. 2. LresNPfin 1(poly1(1), V ar1, Pro2)−FIN 6=∅. 3. REG ⊆LresNPfin 1(poly1(1), V ar∗, Pro∗). 4. LresNPfin 1(poly1(4), V ar4, Pro4)−REG 6=∅.. 5. LresNPfin 1(poly1(4), V ar7, Pro6)−CF 6=∅. 6. The family LresNPfin 1(poly1(4), V ar4, Pro7) contain non-semilinear languages. 7. LrespENPhal 1(poly1(1), V ar2, Pro2)−FIN 6=∅. 8. FIN ⊂LrespENP hal 1(poly1(1), V ar∗, Pro∗). 9. REG ⊆LrespENPhal 1(poly1(2), V ar∗, Pro∗). 10. LrespENPhal 1(poly1(1), V ar6, Pro4)−REG 6=∅. 300 Gh. P˘aun, T. Wu, Z. Zhang 61320106005), Ph.D. Programs Foundation of Ministry of Education of China (2012014213008), and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012). References 1. C. Calude, Gh. P˘aun: Bio-steps beyond Turing, CDMTCS Research Report 226, Univ. of Auckland (November 2003), and BioSystems, 77 (2004), 175–194 2. J. Dassow, G. Vaszil: P finite automata and regular languages over countable infinite alphabets. Proc. WMC 2006, Leiden, The Netherlands (H.J. Hoogeboom et al., eds.), LNCS 4361, Springer, 2006, 367–381. 3. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 4. A. Leporati, A.E. Porreca, C. Zandron, G. Mauri: Improving universality results on parallel enzymatic numerical P systems. Proceedings of 11th Brainstorming Week on Membrane Computing, Sevilla, February 2013, Fenix Editora, Sevilla, 2013, 177–200. 5. A. Leporati, A.E. Porreca, C. Zandron, G. Mauri: Enzymatic numerical P systems using elementary arithmetic operations. Membrane Computing. Proc. 14th Intern. Conf., CMC2013, Chi¸sin˘au, August 2013, LNCS 8340 (A. Alhazov et al., eds.), Springer, Berlin, 2014, 249–264. 6. A.B. Pavel, C.I. Vasile, I. Dumitrache: Robot localization implemented with enzymatic numerical P systems. Proc. Conf. Living Machines 2012, LNCS 7375, Springer, 2012, 204–215. 7. Gh. P˘aun, R. P˘aun: Membrane computing and economics: Numerical P systems. Fundamenta Informaticae, 73 (2006), 213–227. 8. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing. Oxford University Press, 2010. 9. A. Syropoulos: Hypercomputation: Computing Beyond the Church-Turing Barrier. Springer, Berlin, 2008. 10. C.I. Vasile, A.B. Pavel, I. Dumitrache: Universality of enzymatic numerical P systems. International Journal of Computer Mathematics, 90(4) (2013), 869–879. 11. C.I. Vasile, A.B. Pavel, I. Dumitrache, Gh. P˘aun: On the power of enzymatic numerical P systems. Acta Informatica, 49(6) (2012), 395–412. 12. T. Wu, A. P˘aun, Z. Zhang, L. Pan: Spiking neural P systems with polarizations. Submitted, 2015. 13. T. Wu, Z. Zhang, L. Pan: On string languages generated by cell-like spiking neural P systems. Submitted, 2015. 14. T. Wu, Z. Zhang, Gh. P˘aun, L. Pan: Cell-like spiking neural P systems. Submitted, 2015. 15. Z. Zhang, L. Pan: Numerical P systems with production thresholds. Submitted, 2015. 16. Z. Zhang, T. Wu, L. Pan, Gh. P˘aun: On string languages generated by numerical P systems. Submitted, 2015. 17. Z. Zhang, T. Wu, A. P˘aun, L. Pan: Numerical P systems with migrating variables. Submitted, 2015. 18. Z. Zhang, T. Wu, A. P˘aun, L. Pan: Universal enzymatic numerical P systems with a small number of enzymatic variables. Submitted, 2015. 19. Z. Zhang, J. Xu, L. Pan: Numerical P systems with thresholds. Submitted, 2015.