×

Asynchronous spiking neural P systems. (English) Zbl 1168.68014

Summary: We consider here spiking neural P systems with a non-synchronized (i.e., asynchronous) use of rules: in any step, a neuron can apply or not apply its rules which are enabled by the number of spikes it contains (further spikes can come, thus changing the rules enabled in the next step). Because the time between two firings of the output neuron is now irrelevant, the result of a computation is the number of spikes sent out by the system, not the distance between certain spikes leaving the system. The additional non-determinism introduced in the functioning of the system by the non-synchronization is proved not to decrease the computing power in the case of using extended rules (several spikes can be produced by a rule). That is, we obtain again the equivalence with Turing machines (interpreted as generators of sets of (vectors of) numbers). However, this problem remains open for the case of standard spiking neural P systems, whose rules can only produce one spike. On the other hand we prove that asynchronous systems, with extended rules, and where each neuron is either bounded or unbounded, are not computationally complete.
For these systems, the configuration reachability, membership (in terms of generated vectors), emptiness, infiniteness, and disjointness problems are shown to be decidable. However, containment and equivalence are undecidable.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cavaliere, M.; Deufemia, V., Further results on time-free P systems, International Journal of Foundations of Computer Science, 17, 1, 69-90 (2006) · Zbl 1088.68056
[2] Cavaliere, M.; Sburlan, D., Time-independent P systems, (Membrane Computing. International Workshop WMC5, Milano, Italy, 2004. Membrane Computing. International Workshop WMC5, Milano, Italy, 2004, LNCS, vol. 3365 (2005), Springer), 239-258 · Zbl 1117.68355
[3] H. Chen, R. Freund, M. Ionescu, Gh. Păun, M.J. Pérez-Jiménez, On string languages generated by spiking neural P systems, in: [6]; H. Chen, R. Freund, M. Ionescu, Gh. Păun, M.J. Pérez-Jiménez, On string languages generated by spiking neural P systems, in: [6]
[4] H. Chen, T.-O. Ishdorj, Gh. Păun, M.J. Pérez-Jiménez, Spiking neural P systems with extended rules, in: [6]; H. Chen, T.-O. Ishdorj, Gh. Păun, M.J. Pérez-Jiménez, Spiking neural P systems with extended rules, in: [6]
[5] Gerstner, W.; Kistler, W., Spiking Neuron Models. Single Neurons, Populations, Plasticity (2002), Cambridge Univ. Press · Zbl 1100.92501
[6] (Gutiérrez-Naranjo, M. A.; etal., Proceedings of Fourth Brainstorming Week on Membrane Computing, Febr. 2006, Fenix Editora, Sevilla (2006))
[7] Greibach, S., Remarks on blind and partially blind one-way multicounter machines, Theoretical Computer Science, 7, 3, 311-324 (1978) · Zbl 0389.68030
[8] Ibarra, O. H.; Woodworth, S., Characterizations of some restricted spiking neural P systems, (Proc. 7th Workshop on Membrane Computing, Leiden, July 2006. Proc. 7th Workshop on Membrane Computing, Leiden, July 2006, LNCS, vol. 4361 (2006), Springer: Springer Berlin), 424-442 · Zbl 1187.68238
[9] Ibarra, O. H.; Woodworth, S.; Yu, F.; Păun, A., On spiking neural P systems and partially blind counter machines, (Proc. 5th International Conference on Unconventional Computation. Proc. 5th International Conference on Unconventional Computation, LNCS, vol. 4135 (2006), Springer: Springer Berlin), 113-129 · Zbl 1126.68428
[10] O.H. Ibarra, A. Păun, Gh. Păun, A. Rodríguez-Patón, P. Sosik, S. Woodworth, Normal forms for spiking neural P systems, in: [6]; O.H. Ibarra, A. Păun, Gh. Păun, A. Rodríguez-Patón, P. Sosik, S. Woodworth, Normal forms for spiking neural P systems, in: [6] · Zbl 1111.68040
[11] Ibarra, O. H.; Woodworth, S., Characterizations of some classes of spiking neural P systems, Natural Computing, 7, 4, 499-517 (2008) · Zbl 1187.68395
[12] Ionescu, M.; Păun, Gh.; Yokomori, T., Spiking neural P systems, Fundamenta Informaticae, 71, 2-3, 279-308 (2006) · Zbl 1110.68043
[13] Ionescu, M.; Păun, Gh.; Yokomori, T., Spiking neural P systems with exhaustive use of rules, International Journal of Unconventional Computing, 3, 2, 135-154 (2007)
[14] Maass, W., Computing with spikes, Foundations of Information Processing of TELEMATIK, 8, 1, 32-36 (2002), (special issue)
[15] (Maass, W.; Bishop, C., Pulsed Neural Networks (1999), MIT Press: MIT Press Cambridge) · Zbl 0935.68087
[16] Minsky, M., Computation — Finite and Infinite Machines (1967), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0195.02402
[17] A. Păun, Gh. Păun, Small universal spiking neural P systems, in: [6]; A. Păun, Gh. Păun, Small universal spiking neural P systems, in: [6]
[18] Păun, Gh., Membrane Computing — An Introduction (2002), Springer: Springer Berlin · Zbl 1034.68037
[19] Păun, Gh.; Pérez-Jiménez, M. J.; Rozenberg, G., Spike trains in spiking neural P systems, International Journal of Foundations of Computer Science, 17, 4, 975-1002 (2006) · Zbl 1098.68048
[20] (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, 3 Volumes (1997), Springer: Springer Berlin) · Zbl 0866.68057
[21] The P systems web page: http://ppage.psystems.eu; The P systems web page: http://ppage.psystems.eu
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.