Research ArticlesNo Access

Simplified and Yet Turing Universal Spiking Neural P Systems with Communication on Request

Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei 430074, P. R. China

Search for more papers by this author

Florin-Daniel Bîlbîe

Department of Computer Science, Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei Nr. 14, Sector 1, C.P. 010014, Bucharest, Romania

Search for more papers by this author

Andrei Păun

Department of Computer Science, Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei Nr. 14, Sector 1, C.P. 010014, Bucharest, Romania

Department of Bioinformatics, National Institute of Research and Development for Biological Sciences, Splaiul Independenţei, Nr. 296, Sector 6, Bucharest, Romania

Search for more papers by this author

Linqiang Pan

School of Electric and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou, Henan 450002, P. R. China

E-mail Address: lqpan@mail.hust.edu.cn

E-mail Address: lqpanhust@gmail.com

Corresponding author.

Search for more papers by this author

, and

Ferrante Neri

Centre for Computational Intelligence, School of Computer Science and Informatics, De Montfort University, The Gateway, Leicester LE1 9BH, UK

Search for more papers by this author

https://doi.org/10.1142/S0129065718500132Cited by:98 (Source: Crossref)

Abstract

Spiking neural P systems are a class of third generation neural networks belonging to the framework of membrane computing. Spiking neural P systems with communication on request (SNQ P systems) are a type of spiking neural P system where the spikes are requested from neighboring neurons. SNQ P systems have previously been proved to be universal (computationally equivalent to Turing machines) when two types of spikes are considered. This paper studies a simplified version of SNQ P systems, i.e. SNQ P systems with one type of spike. It is proved that one type of spike is enough to guarantee the Turing universality of SNQ P systems. Theoretical results are shown in the cases of the SNQ P system used in both generating and accepting modes. Furthermore, the influence of the number of unbounded neurons (the number of spikes in a neuron is not bounded) on the computation power of SNQ P systems with one type of spike is investigated. It is found that SNQ P systems functioning as number generating devices with one type of spike and four unbounded neurons are Turing universal.

Keywords:

References

1. Y. Zeinali and B. A. Story, Competitive probabilistic neural network, Integr. Comput.-Aided Eng. 24(2) (2017) 105–118. Web of Science, Google Scholar
2. A. Rigos, G. E. Tsekouras, M. I. Vousdoukas, A. Chatzipavlis and A. F. Velegrakis, A Chebyshev polynomial radial basis function neural network for automated shoreline extraction from coastal imagery, Integr. Comput.-Aided Eng. 23(2) (2016) 141–160. Web of Science, Google Scholar
3. J. A. Garrido, N. R. Luque, S. Tolu and E. D’Angelo, Oscillation-driven spike-timing dependent plasticity allows multiple overlapping pattern recognition in inhibitory interneuron networks, Int. J. Neural Syst. 26(05) (2016) 1650020. Link, Web of Science, Google Scholar
4. S. Iliya and F. Neri, Towards artificial speech therapy: A neural system for impaired speech segmentation, Int. J. Neural Syst. 26(6) (2016) 1650023. Link, Web of Science, Google Scholar
5. T. J. Hirschauer, H. Adeli and J. A. Buford, Computer-aided diagnosis of Parkinson’s disease using enhanced probabilistic neural network, J. Med. Syst. 39(11) (2015) 179. Medline, Web of Science, Google Scholar
6. S. Schliebs, N. Kasabov and M. Defoin-Platel, On the probabilistic optimization of spiking neural networks, Int. J. Neural Syst. 20(06) (2010) 481–500. Link, Web of Science, Google Scholar
7. S. Shapero, M. Zhu, J. Hasler and C. Rozell, Optimal sparse approximation with integrate and fire neurons, Int. J. Neural Syst. 24(05) (2014) 1440001. Link, Web of Science, Google Scholar
8. D. R. Freestone, K. J. Layton, L. Kuhlmann and M. J. Cook, Statistical performance analysis of data-driven neural models, Int. J. of Neural Syst. 27(1) (2017) 1650045. Link, Web of Science, Google Scholar
9. D. Gentiletti, P. Suffczynski, V. Gnatkovsky and M. de Curtis, Changes of ionic concentrations during seizure transitions: A modeling study, Int. J. Neural Syst. 27(4) (2017) 1750004. Link, Web of Science, Google Scholar
10. L. Appeltant, M. C. Soriano, G. Van der Sande, J. Danckaert, S. Massar, J. Dambre, C. R. Mirasso and I. Fischer, Information processing using a single dynamical node as complex system, Nat. Commun. 2 (2011) 468. Medline, Web of Science, Google Scholar
11. L. Pigou, S. Dieleman, P.-J. Kindermans and B. Schrauwen, Sign language recognition using convolutional neural networks, in Computer Vision — ECCV 2014 Workshops eds. L. Agapito, M. M. Bronstein and C. Rother (Springer International Publishing, 2015), pp. 572–578. Google Scholar
12. H. T. Huynh, Y. Won and J.-J. Kim, An improvement of extreme learning machine for compact single-hidden-layer feedforward neural networks, Int. J. Neural Syst. 18(05) (2008) 433–441. Link, Web of Science, Google Scholar
13. M. Ahmadlou and H. Adeli, Enhanced probabilistic neural network with local decision circles: A robust classifier, Integr. Comput.-Aided Eng. 17(3) (2010) 197–210. Web of Science, Google Scholar
14. N. Wang and H. Adeli, Self-constructing wavelet neural network algorithm for nonlinear control of large structures, Eng. Appl. Artiff. Intell. 41 (2015) 249–258. Web of Science, Google Scholar
15. W. Maass, Networks of spiking neurons: the third generation of neural network models, Neural Netw. 10(9) (1997) 1659–1671. Web of Science, Google Scholar
16. S. Ghosh-Dastidar and H. Adeli, Spiking neural networks, Int. J. Neural Syst. 19(04) (2009) 295–308. Link, Web of Science, Google Scholar
17. S. M. Bohte, J. N. Kok and H. La Poutre, Error-backpropagation in temporally encoded networks of spiking neurons, Neurocomputing 48(1) (2002) 17–37. Web of Science, Google Scholar
18. F. Ponulak and A. Kasiński, Supervised learning in spiking neural networks with resume: sequence learning, classification, and spike shifting, Neural Comput. 22(2) (2010) 467–510. Medline, Web of Science, Google Scholar
19. O. Booij and H. Tat Nguyen, A gradient descent rule for spiking neurons emitting multiple spikes, Inf. Process. Lett. 95(6) (2005) 552–558. Web of Science, Google Scholar
20. T. J. Strain, L. McDaid, T. M. McGinnity, L. P. Maguire and H. M. Sayers, An STDP training algorithm for a spiking neural network with dynamic threshold neurons, Int. J. Neural Syst. 20(06) (2010) 463–480. Link, Web of Science, Google Scholar
21. F. Montani, A. Oliynyk and L. Fadiga, Superlinear summation of information in premotor neuron pairs, Int. J. Neural Syst. 27(2) (2017) 1650009. Link, Web of Science, Google Scholar
22. S. Ghosh-Dastidar and H. Adeli, Improved spiking neural networks for EEG classification and epilepsy and seizure detection, Integr. Comput.-Aided Eng. 14(3) (2007) 187–212. Web of Science, Google Scholar
23. S. Ghosh-Dastidar and H. Adeli, A new supervised learning algorithm for multiple spiking neural networks with application in epilepsy and seizure detection, Neural Netw. 22(10) (2009) 1419–1431. Medline, Web of Science, Google Scholar
24. A. Mohemmed, S. Schliebs, S. Matsuda and N. Kasabov, SPAN: Spike pattern association neuron for learning spatio-temporal spike patterns, Int. J. Neural Syst. 22(04) (2012) 1250012. Link, Web of Science, Google Scholar
25. E. Nichols, L. McDaid and N. Siddique, Case study on a self-organizing spiking neural network for robot navigation, Int. J. Neural Syst. 20(06) (2010) 501–508. Link, Web of Science, Google Scholar
26. A. Geminiani, C. Casellato, A. Antonietti, E. D’Angelo and A. Pedrocchi, A multiple-plasticity spiking neural network embedded in a closed-loop control system to model cerebellar pathologies, Int. J. Neural Syst. (2017). https://doi.org/10.1142/S0129065717500174 Medline, Web of Science, Google Scholar
27. C. Luo, Y. Zhang, W. Cao, Y. Huang, F. Yang, J. Wang, S. Tu, X. Wang and D. Yao, Altered structural and functional feature of striato-cortical circuit in benign epilepsy with centrotemporal spikes, Int. J. Neural Syst. 25(6) (2015) 1550027. Link, Web of Science, Google Scholar
28. L. Guo, Z. Wang, M. Cabrerizo and M. Adjouadi, A cross-correlated delay shift supervised learning method for spiking neurons with application to interictal spike detection in epilepsy, Int. J. Neural Syst. 27(3) (2017) 1750002. Link, Web of Science, Google Scholar
29. S. Knieling, K. S. Sridharan, P. Belardinelli, G. Naros, D. Weiss, F. Mormann and A. Gharabaghi, An unsupervised online spike-sorting framework, Int. J. Neural Syst. 26(5) (2016) 1550042. Link, Web of Science, Google Scholar
30. A. Morro, V. Canals, A. Oliver, M. Alomar, F. Galán-Prado, P. Ballester and J. Rosselló, A stochastic spiking neural network for virtual screening, IEEE Trans. Neural Netw. Learn. Syst. 29(4) (2017) 1371–1375. Medline, Web of Science, Google Scholar
31. J. L. Rossello, V. Canals, A. Oliver and A. Morro, Studying the role of synchronized and chaotic spiking neural ensembles in neural information processing, Int. J. Neural Syst. 24(05) (2014) 1430003. Link, Web of Science, Google Scholar
32. J. L. Rosselló, M. L. Alomar, A. Morro, A. Oliver and V. Canals, High-density liquid-state machine circuitry for time-series forecasting, Int. J. Neural Syst. 26(5) (2016) 1550036. Link, Web of Science, Google Scholar
33. M. Ionescu, G. Păun and T. Yokomori, Spiking neural P systems, Fundam. Inform. 71(2–3) (2006) 279–308. Web of Science, Google Scholar
34. G. Zhang, H. Rong, F. Neri and M. J. Pérez-Jiménez, An optimization spiking neural P system for approximately solving combinatorial optimization problems, Int. J. Neural Syst. 24(05) (2014) 1440006. Link, Web of Science, Google Scholar
35. G. Păun, Computing with membranes, J. Comput. Syst. Sci. 61(1) (2000) 108–143. Web of Science, Google Scholar
36. G. Păun, Membrane Computing: An Introduction (Springer-Verlag, Berlin, 2012). Google Scholar
37. T. Song, L. Pan, J. Wang, I. Venkat, K. G. Subramanian and R. Abdullah, Normal forms of spiking neural P systems with anti-spikes, IEEE Trans. Nanobiosci. 11 (2012) 352–359. Medline, Web of Science, Google Scholar
38. M. Cavaliere, O. H. Ibarra, G. Păun, O. Egecioglu, M. Ionescu and S. Woodworth, Asynchronous spiking neural P systems, Theor. Comput. Sci. 410(24) (2009) 2352–2364. Web of Science, Google Scholar
39. T. Song, L. Pan and G. Păun, Asynchronous spiking neural P systems with local synchronization, Inf. Sci. 219 (2013) 197–207. Web of Science, Google Scholar
40. G. Păun, M. J. Pérez-Jiménez and G. Rozenberg, Spike trains in spiking neural P systems, Int. J. Found. Comput. Sci. 17(04) (2006) 975–1002. Link, Web of Science, Google Scholar
41. Z. Xu, M. Cavaliere, P. An, S. Vrudhula and Y. Cao, The stochastic loss of spikes in spiking neural P systems: Design and implementation of reliable arithmetic circuits, Fundam. Inform. 134 (2014) 183–200. Web of Science, Google Scholar
42. M. Cavaliere and I. Mura, Experiments on the reliability of stochastic spiking neural P systems, Nat. Comput. 7 (2008) 453–470. Google Scholar
43. A. Păun and G. Păun, Small universal spiking neural P systems, BioSystems 90(1) (2007) 48–60. Medline, Web of Science, Google Scholar
44. H. Chen, R. Freund, M. Ionescu, G. Păun and M. J. Pérez-Jiménez, On string languages generated by spiking neural P systems, Fundam. Inform. 75(1–4) (2007) 141–162. Web of Science, Google Scholar
45. T.-O. Ishdorj and A. Leporati, Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources, Nat. Comput. 7(4) (2008) 519–534. Google Scholar
46. T.-O. Ishdorj, A. Leporati, L. Pan, X. Zeng and X. Zhang, Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources, Theor. Comput. Sci. 411(25) (2010) 2345–2358. Web of Science, Google Scholar
47. L. Pan, G. Păun and M. J. Pérez-Jiménez, Spiking neural P systems with neuron division and budding, Sci. China Inf. Sci. 54(8) (2011) 1596–1607. Google Scholar
48. D. Díaz-Pernil, F. Peña-Cantillana and M. A. Gutiérrez-Naranjo, A parallel algorithm for skeletonizing images by using spiking neural P systems, Neurocomputing 115 (2013) 81–91. Web of Science, Google Scholar
49. H. Peng, J. Wang, M. J. Pérez-Jiménez, H. Wang, J. Shao and T. Wang, Fuzzy reasoning spiking neural P systems for fault diagnosis, Inf. Sci. 235 (2013) 106–116. Web of Science, Google Scholar
50. T. Wang, G. Zhang, J. Zhao, Z. He, J. Wang and M. J. Pérez-Jiménez, Fault diagnosis of electric power systems based on fuzzy reasoning spiking neural P systems, IEEE Trans. Power Syst. 30(3) (2015) 1182–1194. Web of Science, Google Scholar
51. Y. Yahya, A. Qian and A. Yahya, Power transformer fault diagnosis using fuzzy reasoning spiking neural P systems, J. Intell. Learn. Syst. Appl. 8 (2016) 77–91. Google Scholar
52. M. Ionescu and D. Sburlan, Some applications of spiking neural P systems, Comput. Inf. 27(3) (2008) 515–528. Google Scholar
53. T. Song, P. Zheng, M. D. Wong and X. Wang, Design of logic gates using spiking neural P systems with homogeneous neurons and astrocytes-like control, Inf. Sci. 372 (2016) 380–391. Web of Science, Google Scholar
54. C. Diaz, G. Sanchez, G. Duchen, M. Nakano and H. Perez, An efficient hardware implementation of a novel unary spiking neural network multiplier with variable dendritic delays, Neurocomputing 189 (2016) 130–134. Web of Science, Google Scholar
55. B. Schrauwen, M. D’Haene, D. Verstraeten and J. V. Campenhout, Compact hardware liquid state machines on FPGA for real-time speech recognition, Neural Netw. 21(2) (2008) 511–523. Medline, Web of Science, Google Scholar
56. D. Verstraeten, B. Schrauwen and D. Stroobandt, Reservoir computing with stochastic bitstream neurons, in Proc. 16th Annu. ProRISC Workshop (2005), pp. 454–459. Google Scholar
57. M. D’Haene, M. Hermans and B. Schrauwen, Toward unified hybrid simulation techniques for spiking neural networks, Neural Comput. 26(6) (2014) 1055–1079. Medline, Web of Science, Google Scholar
58. E. Csuhaj-Varju, Grammar Systems: A Grammatical Approach to Distribution and Cooperation (Gordon and Breach, London, 1994). Google Scholar
59. G. Păun, Grammar systems: A grammatical approach to distribution and cooperation, in ICALP 1995: Automata, Languages and Programming, eds. Z. Fülöp and F. Gécseg (Springer, Berlin, 1995), pp. 429–443. Google Scholar
60. L. Pan, G. Păun, G. Zhang and F. Neri, Spiking neural P systems with communication on request, Int. J. Neural Syst. 27(08) (2017) 1750042. Link, Web of Science, Google Scholar
61. Z. Wang, L. Guo and M. Adjouadi, A generalized leaky integrate-and-fire neuron model with fast implementation method, Int. J. Neural Syst. 24(05) (2014) 1440004. Link, Web of Science, Google Scholar
62. A. Leporati, C. Zandron, C. Ferretti and G. Mauri, On the computational power of spiking neural P systems, Int. J. Unconv. Comput. 5(5) (2009) 459–473. Web of Science, Google Scholar
63. M. García Arnau, D. Peréz, A. Rodríguez Patón and P. Sosík, Spiking neural P systems: stronger normal forms, Int. J. Unconv. Comput. 5 (2009) 411–425. Web of Science, Google Scholar
64. J. Wang, H. J. Hoogeboom, L. Pan, G. Păun and M. J. Pérez-Jiménez, Spiking neural P systems with weights, Neural Comput. 22(10) (2010) 2615–2646. Medline, Web of Science, Google Scholar
65. T. Wu, A. Păun, Z. Zhang and L. Pan, Spiking neural P systems with polarizations, IEEE Trans. Neural Netw. Learn. Syst. (2017). https://doi.org/10.1109/TNNLS.2017.2726119 Google Scholar
66. G. Păun, G. Rozenberg and A. Salomaa, The Oxford Handbook of Membrane Computing (Oxford University Press, New York, 2010). Google Scholar
67. G. Rozenberg and A. Salomaa (eds.), Handbook of Formal Languages (Springer-Verlag, Berlin, 1997). Google Scholar
68. J. E. Hopcroft, R. Motwani and J. D. Ullman (eds.), Introduction to Automata Theory, Languages, and Computation, 3rd Edition (Pearson Education, New Jersey, 2001). Google Scholar
69. A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc. 2(42) (1936) 230–265. Google Scholar
70. M. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, 1967). Google Scholar
71. I. Korec, Small universal register machines, Theor. Comput. Sci. 168(2) (1996) 267–301. Web of Science, Google Scholar
72. F.-D. Bîlbîe and A. Păun, Universality of spiking neural P systems with communication on request using one type of spike, in Proc. 18th Int. Conf. Membrane Computing (CMC 2017) (2017). Google Scholar
73. H. T. Siegelmann and E. D. Sontag, On the computational power of neural nets, J. Comput. Syst. Sci. 50(1) (1995) 132–150. Web of Science, Google Scholar
74. A. Gupta and L. N. Long, Character recognition using spiking neural networks, in Proc. 2007 Int. Joint Conf. Neural Networks (2007), pp. 53–58. Google Scholar