On the computational complexity of spiking neural P systems
From MaRDI portal
Publication:609034
DOI10.1007/S11047-010-9213-1zbMATH Open1207.68141arXiv0912.0928OpenAlexW2397533176MaRDI QIDQ609034FDOQ609034
Authors: Turlough Neary 
Publication date: 30 November 2010
Published in: Natural Computing (Search for Journal in Brave)
Abstract: It is shown that there is no standard spiking neural P system that simulates Turing machines with less than exponential time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent of the input length. Following this we construct a universal spiking neural P system with exhaustive use of rules that simulates Turing machines in linear time and has only 10 neurons.
Full work available at URL: https://arxiv.org/abs/0912.0928
Recommendations
- On the Computational Complexity of Spiking Neural P Systems
- Computability of spiking neural P systems with anti-spikes
- Polynomial complexity classes in spiking neural P systems
- On spiking neural P systems
- Spiking neural P systems: theoretical results and applications
- On the computational power of circuits of spiking neurons
- Spiking Neural P Systems: Some Characterizations
- Solving Numerical NP-Complete Problems with Spiking Neural P Systems
- Computational power of sequential spiking neural P systems with multiple channels
computational complexityspiking neural P systemlinear timesmall universal spiking neural P systemtime efficient spiking neural P system
Cites Work
Cited In (17)
- Time features in the computational power of spiking neural P systems
- Universality of SNQ P systems using one type of spikes and restrictive rule application
- Universality of graph-controlled leftist insertion-deletion systems with two states
- Small SNQ P systems with multiple types of spikes
- Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits
- On spiking neural P systems and partially blind counter machines
- On the Computational Complexity of Spiking Neural P Systems
- On the Computational Power of Threshold Circuits with Sparse Activity
- Three small universal spiking neural P systems
- Polynomial complexity classes in spiking neural P systems
- Universal Sleptsov net
- Computing the Maximum Bisimulation with Spiking Neural P Systems
- Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources
- On solutions and representations of spiking neural P systems with rules on synapses
- Novel systematic mathematical computation based on the spiking frequency gate (SFG): innovative organization of spiking computer
- Title not available (Why is that?)
- Sequentiality induced by spike number in SNP systems: small universal machines
This page was built for publication: On the computational complexity of spiking neural P systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q609034)
