Skip to main content
Springer Nature Link
Log in

Computing with Spikes and Membranes: Computability and Complexity in Spiking Neural P Systems

  • Conference paper
  • First Online:
Save conference paper
View saved research
Timeless Machines: Computability Across Eras (CiE 2026)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 16674))

Included in the following conference series:

  • 16 Accesses

Abstract

Spiking neural P systems are formal models of computation inspired by the structure and connections of neural networks and how information is transmitted through energy pulses or spikes. This contribution presents a theoretical overview of spiking neural P systems and some interesting properties of this framework which lies in the area of membrane computing. We first recall the basic ingredients of the model, including spikes, rules, synapses, configurations, and derivation modes. We also examine the usual ideas behind the proofs of completeness and universality, mostly by simulation of universal models. Apart from computability issues, some computational complexity aspects, especially concerning time, will be introduced. We then discuss how complexity-theoretic questions can be formulated in this setting, with special attention to time, precomputed resources, uniformity, and the time–space trade-off. Since SNP systems are related to the third generation of neural network models, special attention is paid to the representation of information, including input/output encodings based on spike multiplicities and temporal patterns. Finally, some representative variants and extensions, as well as open problems related to both computability and complexity-theoretic characterizations, will be discussed. In general, spiking neural P systems are presented as a formal laboratory for studying computation through the interaction of signals, time, and structure.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 69.99
Price excludes VAT (USA)
Softcover Book
USD 89.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. 1.

    The notation is the same used in the original paper [6].

  2. 2.

    In the paper, the number of variables is 2n, for the sake of simplicity, we use here only n.

  3. 3.

    Some of these ideas are elaborated in the field of automatic design of spiking neural P systems. Some information about this research can be found in Chap. 5 of [46].

References

  1. Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266(5187), 1021–1024 (1994)

    Article  Google Scholar 

  2. Alhazov, A., Freund, R., Ivanov, S., Oswald, M., Verlan, S.: Extended spiking neural P systems with white hole rules and their red-green variants. Nat. Comput. 17(2), 297–310 (2018)

    Article  MathSciNet  Google Scholar 

  3. Alhazov, A., Freund, R., Oswald, M., Slavkovik, M.: Extended spiking neural P systems. In: Hoogeboom, H.J., Păun, Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, pp. 123–134. Springer, Heidelberg (2006)

    Google Scholar 

  4. Cabarle, F.G.C.: Thinking about spiking neural P systems: some theories, tools, and research topics. J. Membr. Comput. 6(2), 148–167 (2024)

    Article  MathSciNet  Google Scholar 

  5. Cabarle, F.G.C., Adorna, H.N., Pérez-Jiménez, M.J., Song, T.: Spiking neural P systems with structural plasticity. Neural Comput. Appl. 26(8), 1905–1917 (2015)

    Article  Google Scholar 

  6. Chen, H., Ionescu, M., Ishdorj, T.: On the efficiency of spiking neural P systems. In: Proceedings of the Fourth Brainstorming Week on Membrane Computing, pp. 195–206. Sevilla, Spain (2006)

    Google Scholar 

  7. Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computing, 2 edn. Springer (2015)

    Google Scholar 

  8. Frisco, P., Gheorghe, M., Pérez-Jiménez, M.J. (eds.): Applications of Membrane Computing in Systems and Synthetic Biology. ECC, vol. 7. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-03191-0

  9. Haykin, S.: Neural Networks and Learning Machines, 3 edn. Pearson Education India (2009)

    Google Scholar 

  10. Hirvensalo, M.: Quantum Computing. Springer (2013)

    Google Scholar 

  11. Indiveri, G., Liu, S.C.: Memory and information processing in neuromorphic systems. Proc. IEEE 103(8), 1379–1397 (2015)

    Article  Google Scholar 

  12. Ionescu, M., Păun, Gh., Yokomori, T.: Spiking neural P systems. Fundamenta Informaticae 71(2–3), 279–308 (2006)

    Google Scholar 

  13. Ishdorj, T.O., Leporati, A., Pan, L., Zeng, X., Zhang, X.: Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theoret. Comput. Sci. 411(25), 2345–2358 (2010)

    Article  MathSciNet  Google Scholar 

  14. Istrail, S., De-Leon, S.B.T., Davidson, E.H.: The regulatory genome and the computer. Dev. Biol. 310(2), 187–195 (2007)

    Article  Google Scholar 

  15. Jiménez, M.J.P., Jiménez, Á.R., Caparrini, F.S.: Complexity classes in models of cellular computing with membranes. Nat. Comput. 2(3), 265–285 (2003)

    Article  MathSciNet  Google Scholar 

  16. Leporati, A., Zandron, C., Ferretti, C., Mauri, G.: On the computational power of spiking neural P systems. In: Proceedings of the Fifth Brainstorming Week on Membrane Computing, pp. 227–245. Sevilla, Spain (2007)

    Google Scholar 

  17. Leporati, A., Mauri, G., Zandron, C.: Spiking neural P systems: main ideas and results. Nat. Comput. 21(4), 629–649 (2022)

    Article  MathSciNet  Google Scholar 

  18. Leporati, A., Mauri, G., Zandron, C., Păun, Gh., Pérez-Jiménez, M.J.: Uniform solutions to SAT and Subset Sum by spiking neural P systems. Nat. Comput. 8(4), 681–702 (2009)

    Article  MathSciNet  Google Scholar 

  19. Maass, W.: Networks of spiking neurons: the third generation of neural network models. Neural Netw. 10(9), 1659–1671 (1997)

    Article  Google Scholar 

  20. Martín-Vide, C., Păun, Gh., Pazos, J., Rodríguez-Patón, A.: Tissue P systems. Theor. Comput. Sci. 296(2), 295–326 (2003)

    Google Scholar 

  21. McCulloch, W.S., Pitts, W.: A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys. 5, 115–133 (1943)

    Article  MathSciNet  Google Scholar 

  22. Orellana-Martín, D., Martínez-del Amor, M.A., Valencia-Cabrera, L., Pérez-Hurtado, I., Riscos-Núñez, A., Pérez-Jiménez, M.J.: Dendrite P systems toolbox: representation, algorithms and simulators. Int. J. Neural Syst. 31(01), 2050071 (2021)

    Article  Google Scholar 

  23. Pan, L., Păun, Gh., Pérez-Jiménez, M.J.: Spiking neural P systems with neuron division and budding. SCIENCE CHINA Inf. Sci. 54(8), 1596–1607 (2011)

    Article  MathSciNet  Google Scholar 

  24. Pan, L., Wang, J., Hoogeboom, H.J.: Spiking neural P systems with astrocytes. Neural Comput. 24(3), 805–825 (2012)

    Article  MathSciNet  Google Scholar 

  25. Păun, Gh.: Computing with Membranes. TUCS Research Report 208, Turku Centre for Computer Science, Turku, Finland (1998)

    Google Scholar 

  26. Păun, Gh.: Computing with membranes. J. Comput. Syst. Sci. 61(1), 108–143 (2000)

    Article  MathSciNet  Google Scholar 

  27. Păun, Gh.: Computing with membranes: attacking NP-complete problems. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, UMC’2K, pp. 94–115. Springer, London (2001)

    Google Scholar 

  28. Păun, Gh., Pérez-Jiménez, M.J., Riscos-Núñez, A.: Tissue P systems with cell division. Int. J. Comput. Commun. Control 3(3), 295–303 (2008)

    Article  Google Scholar 

  29. Păun, Gh., Rozenberg, G., Salomaa, A. (eds.): The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford (2010)

    Google Scholar 

  30. Peng, H., Wang, J.: Advanced Spiking Neural P Systems. Springer (2024)

    Google Scholar 

  31. Peng, H., et al.: Spiking neural P systems with multiple channels. Neural Netw. 95, 66–71 (2017)

    Article  Google Scholar 

  32. Pérez-Jiménez, M.J., Graciani, C., Orellana-Martín, D., Riscos-Núñez, A., Romero-Jiménez, Á., Valencia-Cabrera, L.: Fuzzy reasoning spiking neural P systems revisited: a formalization. Theor. Comput. Sci. 701, 216–225 (2017), at the intersection of computer science with biology, chemistry and physics - In Memory of Solomon Marcus

    Google Scholar 

  33. Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems, vol. 90. Academic Press (1980)

    Google Scholar 

  34. Rumelhart, D.E., Hinton, G.E., Williams, R.J.: Learning representations by back-propagating errors. Nature 323, 533–536 (1986)

    Article  Google Scholar 

  35. Song, B., Li, K., Orellana-Martín, D., Pérez-Jiménez, M.J., PéRez-Hurtado, I.: A survey of nature-inspired computing: membrane computing. ACM Comput. Surv. 54(1) (2021)

    Google Scholar 

  36. Song, T., Pan, L., Păun, Gh.: Spiking neural P systems with rules on synapses. Theoret. Comput. Sci. 529, 82–95 (2014)

    Article  MathSciNet  Google Scholar 

  37. Song, T., Rodríguez-Patón, A., Zheng, P., Zeng, X.: Spiking neural P systems with colored spikes. IEEE Trans. Cogn. Dev. Syst. 10(4), 1106–1115 (2018)

    Article  Google Scholar 

  38. Song, X., et al.: Spiking neural P systems with multiple channels and anti-spikes. Biosystems 169–170, 13–19 (2018)

    Article  Google Scholar 

  39. Sosík, P., Paul, P., Ciencialová, L.: A survey on learning models of spiking neural membrane systems. Nat. Comput. 24(3), 665–677 (2025)

    Article  MathSciNet  Google Scholar 

  40. Sosík, P., Rodríguez-Patón, A., Ciencialová, L.: Polynomial complexity classes in spiking neural P systems. In: Gheorghe, M., Hinze, T., Păun, Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, pp. 348–360. Springer, Heidelberg (2011)

    Google Scholar 

  41. Wang, J., Hoogeboom, H.J., Pan, L.: Spiking neural P systems with neuron division. In: Gheorghe, M., Hinze, T., Păun, Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, pp. 361–376. Springer, Heidelberg (2011)

    Google Scholar 

  42. Wang, T., Zhang, G., Zhao, J., He, Z., Wang, J., Pérez-Jiménez, M.J.: Application of fuzzy reasoning spiking neural P systems to fault diagnosis. Int. J. Comput. Commun. Control 9(5), 636–644 (2014)

    Google Scholar 

  43. Wolfram, S.: A new kind of science. Appl. Mech. Rev. 56(2), B18–B19 (2003)

    Google Scholar 

  44. Wu, T., Pan, L.: Spiking neural P systems with communication on request and mute rules. IEEE Trans. Parallel Distrib. Syst. 34(2), 734–745 (2023)

    Article  Google Scholar 

  45. Zhang, G., et al.: Membrane Computing Models: Implementations. Springer, Singapore (2021)

    Google Scholar 

  46. Zhang, G., et al.: Spiking Neural P Systems. Springer (2024)

    Google Scholar 

Download references

Acknowledgments

This work is part of a project that has received funding from the European Union’s Horizon Europe Research and Innovation Programme under the Marie Skłodowska-Curie Actions (MSCA), Grant Agreement No. 101236749.

Author information

Authors and Affiliations

  1. Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain

    David Orellana-Martín

  2. SCORE Lab, I3US, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain

    David Orellana-Martín

Authors
  1. David Orellana-Martín
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to David Orellana-Martín.

Editor information

Editors and Affiliations

  1. Universität der Bundeswehr München, Neubiberg, Germany

    Vasco Brattka

  2. Universität Trier, Trier, Germany

    Henning Fernau

  3. University of Amsterdam, Amsterdam, The Netherlands

    Lorenzo Galeotti

Ethics declarations

Disclosure of Interests

The author has no competing interests to declare that are relevant to the content of this article.

Rights and permissions

Reprints and permissions

Copyright information

© 2027 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Orellana-Martín, D. (2027). Computing with Spikes and Membranes: Computability and Complexity in Spiking Neural P Systems. In: Brattka, V., Fernau, H., Galeotti, L. (eds) Timeless Machines: Computability Across Eras. CiE 2026. Lecture Notes in Computer Science, vol 16674. Springer, Cham. https://doi.org/10.1007/978-3-032-31348-5_4

Download citation

Keywords

Publish with us

Policies and ethics