Universality of sequential spiking neural P systems based on minimum spike number

Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. Each neuron can have several spiking rules and forgetting rules and neurons work in parallel in the sense that each neuron that can fire should fire at each computation step. In this work, we consider SN P systems working in the sequential way, where the sequentiality is induced by the minimum number of spikes: at each step, one (resp. all) of the neurons with the minimum number of spikes among the neurons that are active (can fire) will fire, called min-sequentiality (resp. min-pseudo-sequentiality). We prove that SN P systems working in min-sequentiality or min-pseudo-sequentiality are universal as both number generating and accepting devices, where the computation results are encoded by the time elapsed between the first two spikes of the output neuron. The results give positive answers to two open problems formulated in [O.H. Ibarra, A. Păun, A. Rodríguez-Patón, Sequential SNP systems based on min/max spike number, Theoretical Computer Science 410 (30–32) (2009) 2982–2991].