On string languages generated by spiking neural P systems with exhaustive use of rules
Tóm tắt
We continue the study of (extended) spiking neural P systems with exhaustive use of rules by considering these computing devices as language generators. Specifically, a step is associated with a symbol according to the number of spikes emitted by the output neuron and the sequence of these symbols associated with a halting computation constitutes a string. Two cases are considered: one of them interprets a step when no spike is emitted as a specified symbol, the other interprets such a step as the empty string. In both cases, it is proved that finite and recursively enumerable languages are characterized by extended spiking neural P systems working in the exhaustive mode. The relationships with regular languages are also investigated.
Tài liệu tham khảo
Chen H, Ionescu M, Ishdorj TO, Păun A, Păun Gh, Pérez-Jiménez MJ (2006) Spiking neural P systems with extended rules. 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, pp 241–266. Fénix Editora
Chen H, Freund R, Ionescu M, Păun Gh, Pérez-Jiménez MJ (2007) On string languages generated by spiking neural P systems. Fundamenta Informaticae 75:141–162
Ibarra OH, Păun A, Păun Gh, Rodríguez-Patón A, Sosík P, Woodworth S (2007) Normal forms for spiking neural P systems. Theor Comput Sci 372(2–3):196–217
Ionescu M, Păun Gh, Yokomori T (2006) Spiking neural P systems. Fundamenta Informaticae 71(2–3):279–308
Ionescu M, Păun Gh, Yokomori T (2007) Spiking neural P systems with exhaustive use of rules. Int J Unconvent Comput 3(2):135–154
Minsky M (1967) Computation—finite and infinite machines. Prentice Hall, Englewood Cliffs
Păun Gh (2002) Membrane computing—an introduction. Springer-Verlag, Berlin
Păun Gh (2007) Twenty six research topics about spiking neural P systems. In: Gutierrez-Naranjo MA, Păun Gh, Romero-Jiménez A, Riscos-Núñez A (eds) Fifth brainstorming week on membrane computing, RGNC Report 01/2007, Research Group on Natural Computing, Sevilla University, pp 263–280, Fénix Editora
Păun Gh, Pérez-Jiménez MJ, Rozenberg G (2006) Spike trains in spiking neural P systems. Int J Found Comput Sci 17(4):975–1002