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.
|
 |
Asynchronous Spiking Neural P Systems: Decidability and Undecidability
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 4848/2008 |
| Book | DNA Computing |
| DOI | 10.1007/978-3-540-77962-9 |
| Copyright | 2008 |
| ISBN | 978-3-540-77961-2 |
| DOI | 10.1007/978-3-540-77962-9_26 |
| Pages | 246-255 |
| Subject Collection | Computer Science |
| SpringerLink Date | Saturday, February 09, 2008 |
| |
|
Asynchronous Spiking Neural P Systems: Decidability and Undecidability
Matteo Cavaliere1 , Omer Egecioglu2 , Oscar H. Ibarra2 , Mihai Ionescu3 , Gheorghe Păun4 and Sara Woodworth2 
| (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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|