Abstract. We consider extended variants of spiking neural P systems and show how these extensions of the original model allow for easy proofs of the computational completeness of extended spiking neural P systems and for the characterization of semilinear sets and regular languages by finite extended spiking neural P systems (defined by having only finite sets of rules assigned to the cells) with only a bounded number of neurons.
Just recently, a new variant of P systems was introduced based on the biological background of neurons sending electrical impulses along axons to other neurons. This biological background had already led to several models in the area of neural computation, e.g., see Maass, Maassed, and spikesbook.
In the area of P systems, one basic model considers hierarchical membrane structures, whereas in another important model cells are placed in the nodes of a graph (which variant was first considered in tissuegraph; tissue P systems then were further elaborated, for example, in tissuechannel and tissuenew). Based on the structure of this model of tissue P systems, in spiking the new model of spiking neural P systems was introduced. The reader is referred to this seeding paper for the interesting details of the biological motivation for this kind of P systems; we will recall just a few of the most important features:
In spiking neural P systems, the contents of a cell (neuron) consists of a number of so-called spikes. The rules assigned to a cell allow us to send information to other neurons in the form of electrical impulses (also called spikes) which are summed up at the target cell; the application of the rules depends on the contents of the neuron and in the general case is described by regular sets. As inspired from biology, the cell sending out spikes may be "closed" for a specific time period corresponding to the refraction period of a neuron; during this refraction period, the neuron is closed for new input and cannot get excited "fire" for spiking again.
The length of the axon may cause a time delay before a spike arrives at the target. Moreover, the spikes coming along different axons may cause effects of different magnitude. We shall include these features in our extended model of spiking neural P systems considered below. Some other features also motivated from biology will be discussed, too, e.g., the use of inhibiting neurons and spikes, respectively. From a mathematical point of view, the most important theoretical feature we shall include in our model of extended spiking neural P systems is that we allow the neurons to send spikes along the axons with different magnitudes at different moments of time.
In spiking the output of a spiking neural P system was considered to be the time between two spikes in a designated output cell. It was shown how spiking neural P systems in that way can generate any recursively enumerable set of natural numbers. Moreover, a characterization of semilinear sets was obtained by spiking neural P system with a bounded number of spikes in the neurons. These results can also be obtained with even more restricted forms of spiking neural P systems, e.g., no time delay (refraction period) is needed, as it was shown in normalformsspiking.
In omegaspiketrains, the behaviour of spiking neural P systems on infinite strings and the generation of infinite sequences of 0 and 1 (the case when the output neuron spikes) was investigated. Finally, in stringspiking, the generation of strings (over the binary alphabet 0 and 1) by spiking neural P systems was investigated; due to the restrictions of the original model of spiking neural P systems, even specific finite languages cannot be generated, but on the other hand, regular languages can be represented as inverse-morphic images of languages generated by finite spiking neural P systems, and even recursively enumerable languages can be characterized as projections of inverse-morphic images of languages generated by spiking neural P systems. The problems occurring in the proofs are also caused by the quite restricted way the output is obtained from the output neuron as sequence of symbols 0 and 1 . The strings of a regular or recursively enumerable language could be obtained directly by collecting the spikes sent by specific output neurons for each symbol.
In the extended model introduced in this paper, we shall use a specific output neuron for each symbol. Computational completeness can be obtained by simulating register machines as in the proofs elaborated in the papers mentioned above, yet in an easier way using only a bounded number of neurons. Moreover, regular languages can be characterized by finite extended spiking neural P systems; again, only a bounded number of neurons is really needed.
Read the complete paper (Artiom ALHAZOV, Rudolf FREUND, Marion OSWALD, Marija SLAVKOVIK: Extended Spiking Neural P Systems Generating Strings and Vectors of Non-Negative Integers): gspikingf.pdf
stringspiking: Chen H, Freund R, Ionescu M, Pãun Gh, Pérez-Jiménez~MJ (2006) On String Languages Generated by Spiking Neural P Systems. In: Gutiérrez-Naranjo MA, Pãun Gh, Riscos-Núñez A, Romero-Campero FJ (eds) Fourth Brainstorming Week on Membrane Computing, Vol. I RGNC REPORT 02/2006, Research Group on Natural Computing, Sevilla University, Fénix Editora, 169-194
DassowPaun: Dassow J, Pãun Gh (1989) Regulated Rewriting in Formal Language Theory. Springer, Berlin
DCFS05: Fernau H, Freund R, Oswald M, Reinhardt K (2005) Refining the Nonterminal Complexity of Graph-controlled Grammars. In: Mereghetti C,Palano B, Pighizzini G, Wotschke D (eds) Seventh International Workshop on Descriptional Complexity of Formal Systems, 110-121
membranechannels: Freund R, Oswald M (2003) P Systems with activated/prohibited membrane channels. In: Pãun Gh , Rozenberg G, Salomaa A, Zandron C (eds) Membrane Computing. International Workshop WMC 2002, Curtea de Arges, Romania. Lecture Notes in Computer Science 2597, Springer, Berlin, 261-268.
FreundOswald01: Freund R, Oswald M (2002) GP Systems with Forbidding Context. Fundamenta Informaticae 49: 81-102
FreundPaun2002: Freund R, Pãun Gh (2004) From Regulated Rewriting to Computing with Membranes: Collapsing Hierarchies. Theoretical Computer Science 312: 143-188
tissuechannel: Freund R, Pãun Gh, Pérez-Jiménez MJ (2004) Tissue-like P systems with channel states. Theoretical Computer Science 330: 101-116
spikesbook: Gerstner W, Kistler W (2002) Spiking Neuron Models. Single Neurons, Populations, Plasticity. Cambridge Univ. Press
Ibarra: Ibarra O, Dang Z, Egecioglu O (2004) Catalytic P systems, semilinear sets, and vector addition systems. Theoretical Computer Science 312, 2-3: 379-399
normalformsspiking: Ibarra OH, Pãun A, Pãun Gh, Rodríguez-Patón A, Sosík P, Woodworth S (2006) Normal Forms for Spiking Neural P Systems. In: In: Gutiérrez-Naranjo MA, Pãun Gh, Riscos-Núñez A, Romero-Campero FJ (eds) Fourth Brainstorming Week on Membrane Computing, Vol. II RGNC REPORT 02/2006, Research Group on Natural Computing, Sevilla University, Fénix Editora, 105-136
spiking: Ionescu M, Pãun Gh, Yokomori T (2006) Spiking neural P systems. Fundamenta Informaticae 71, 2-3: 279-308
Maass: Maass W (2002) Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK 8, 1: 32-36
Maassed: Maass W, Bishop C (eds) (1999) Pulsed Neural Networks. MIT Press, Cambridge
tissuenew: Martín-Vide C, Pazos J, Pãun Gh, Rodríguez-Patón A (2002) A new class of symbolic abstract neural nets: Tissue P systems. In: Proceedings of COCOON 2002, Singapore, Lecture Notes in Computer Science 2387, Springer-Verlag, Berlin, 290-299
Minsky: Minsky ML (1967) Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, New Jersey
Pbook: Pãun Gh (2002) Computing with Membranes: An Introduction. Springer, Berlin
spiketrains: Pãun Gh, Pérez-Jiménez MJ, Rozenberg G (2006) Spike trains in spiking neural P systems, Intern J Found Computer Sci, to appear (also available at Ppage)
omegaspiketrains: Pãun Gh, Pérez-Jiménez MJ, Rozenberg G (2006) Infinite spike trains in spiking neural P systems. Submitted
tissuegraph: Pãun Gh, Sakakibara Y, Yokomori T (2006) P systems on graphs of restricted forms. Publicationes Mathematicae Debrecen 60: 635-660
handbook: Rozenberg G, Salomaa A (eds) (1997) Handbook of Formal Languages (3 volumes). Springer, Berlin
Ppage: The P Systems Web Page, http://psystems.disco.unimib.it