On String Languages Generated by Spiking Neural P Systems

• Autorzy: Chen H. , Freund R. , Ionescu M. , Paun G. , Pérez-Jiménez M.J.
• Języki publikacji: EN

Abstrakty

EN

We continue the study of spiking neural P systems by considering these computing devices as binary string generators: the set of spike trains of halting computations of a given system constitutes the language generated by that system. Although the "direct" generative capacity of spiking neural P systems is rather restricted (some very simple languages cannot be generated in this framework), regular languages are inverse-morphic images of languages of finite spiking neural P systems, and recursively enumerable languages are projections of inverse-morphic images of languages generated by spiking neural P systems.

Słowa kluczowe

EN

membrane computing; spiking neural P systems; Chomshy hierarchy

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 75, nr 1-4
• Strony: 141--162
• Opis fizyczny: bibliogr. 18 poz., rys.

Twórcy

autor

Chen H.

autor

Freund R.

autor

Ionescu M.

autor

Paun G.

autor

Pérez-Jiménez M.J.

• Institute of Mathematics of the Romanian Academy, , PO Box 1-764, 014700 Bucharest , Romania,

Bibliografia

• [1] J. Dassow, Gh. Pǎun: Regulated Rewriting in Formal Language Theory. Springer-Verlag, Berlin, 1989.
• [2] J. Engelfriet, G. Rozenberg: Fixed point languages, equality languages, and representations of recursively enumerable languages. Journal of the ACM, 27 (1980), 499-518.
• [3] R. Freund: Bidirectional sticker systems and representations of RE languages by copy languages. In Computing with Bio-Molecules. Theory and Experiments (Gh. P˘aun, ed.), Springer-Verlag, Singapore, 1998, 182-199.
• [4] W. Gerstner, W. Kistler: Spiking Neuron Models. Single Neurons, Populations, Plasticity. Cambridge Univ. Press, 2002.
• [5] D. Hauschild, M. Jantzen: Petri nets algorithms in the theory of matrix grammars. Acta Informatica, 31 (1994), 719-728.
• [6] O.H. Ibarra, A. Pǎun, Gh. Pǎun, A. Rodríguez-Patón, P. Sosík, S. Woodworth: Normal forms for spiking neural P systems. Theoretical Computer Sci., to appear.
• [7] M. Ionescu, Gh. Pǎun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279-308.
• [8] W. Maass: Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 8, 1 (2002), 32-36.
• [9] W. Maass, C. Bishop, eds.: Pulsed Neural Networks, MIT Press, Cambridge, 1999.
• [10] M. Minsky: Computation - Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967.
• [11] Gh. Pǎun: Membrane Computing - An Introduction. Springer-Verlag, Berlin, 2002.
• [12] Gh. Pǎun, M.J. Pérez-Jiménez, G. Rozenberg: Spike trains in spiking neural P systems. Intern. J. Found. Computer Sci., 17, 4 (2006), 975-1002.
• [13] Gh. Pǎun, M.J. Pérez-Jiménez, G. Rozenberg: Infinite spike trains in spiking neural P systems. Submitted, 2006.
• [14] Z. Pawlak: Rough Sets. Theoretical Aspects of Reasoning About Data. Kluwer, Dordrecht, 1991.
• [15] Z. Pawlak: A treatise on rough sets. In Transactions on Rough Sets (J.F. Peters, A. Skowron, eds.), LNCS 3700, Springer-Verlag, Berlin, 2005, 1-17.
• [16] G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages, 3 volumes. Springer-Verlag, Berlin, 1997.
• [17] A. Salomaa: Formal Languages. Academic Press, New York, 1973.
• [18] The P Systems Web Page: http://psystems.disco.unimib.it.