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. © 2009 Elsevier B.V. All rights reserved.

Asynchronous spiking neural P systems / Cavaliere, M.; Ibarra, O. H.; Paun, G.; Egecioglu, O.; Ionescu, M.; Woodworth, S.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 410:24-25(2009), pp. 2352-2364. [10.1016/j.tcs.2009.02.031]

Asynchronous spiking neural P systems

Cavaliere M.;
2009

Abstract

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. © 2009 Elsevier B.V. All rights reserved.
2009
410
24-25
2352
2364
Asynchronous spiking neural P systems / Cavaliere, M.; Ibarra, O. H.; Paun, G.; Egecioglu, O.; Ionescu, M.; Woodworth, S.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 410:24-25(2009), pp. 2352-2364. [10.1016/j.tcs.2009.02.031]
Cavaliere, M.; Ibarra, O. H.; Paun, G.; Egecioglu, O.; Ionescu, M.; Woodworth, S.
File in questo prodotto:
File Dimensione Formato  
TR-09-2007.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 323.07 kB
Formato Adobe PDF
323.07 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1319961
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 145
  • ???jsp.display-item.citation.isi??? 129
social impact