Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Asynchronous Spiking Neural P Systems: Decidability and Undecidability

Matteo CavaliereContact Information, Omer EgeciogluContact Information, Oscar H. IbarraContact Information, Mihai IonescuContact Information, Gheorghe PăunContact Information and Sara WoodworthContact Information

(1)  Microsoft Research-University of Trento CoSBi, Italy
(2)  Dept. of Computer Science, University of California, Santa Barbara, USA
(3)  Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, Spain
(4)  Institute of Mathematics of the Romanian Academy, Bucharest, Romania
Abstract
In search for “realistic” bio-inspired computing models, we consider asynchronous spiking neural P systems, in the hope to get a class of computing devices with decidable properties. However, although the non-synchronization is known in general to decrease the computing power, in the case of using extended rules (several spikes can be produced by a rule) we obtain again the equivalence with Turing machines (interpreted as generators of sets of vectors of numbers). The problem remains open for the case of restricted spiking neural P systems, whose rules can only produce one spike. On the other hand, we prove that asynchronous spiking neural P systems, with a specific way of halting, using extended rules and where each neuron is either bounded or unbounded, are equivalent to partially blind counter machines and, therefore, have many decidable properties.

Contact Information Matteo Cavaliere
Email: cavaliere@cosbi.eu

Contact Information Omer Egecioglu
Email: omer@cs.ucsb.edu

Contact Information Oscar H. Ibarra
Email: ibarra@cs.ucsb.edu

Contact Information Mihai Ionescu
Email: armandmihai.ionescu@urv.cat

Contact Information Gheorghe Păun
Email: george.paun@imar.ro

Contact Information Sara Woodworth
Email: swood@cs.ucsb.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.112 • Server: mpweb23
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)