Spiking neural P systems are parallel and distributed computation devices which are inspired by the neuro-physiological behavior of biological neurons. In this paper we will present, with a tutorial approach, the main underlying ideas and the most interesting variants that have been proposed in the literature. In particular, we will discuss the results on the computational power of these models, both in terms of Turing completeness and of efficiency in solving hard problems, under different assumptions for information encoding, form and application of rules, and bounds on the main parameters defining the systems.
1 December 2017 in Journal of Computer and System Sciences
P systems with active membranes have been widely used to attack problems in \({\mathbf{NP}}\) or even in \({{\mathbf{PSPACE }}}\); in general, an exponential amount of space is generated in polynomial time by dividing existing membranes. Natural questions arise in this framework, concerning the power of P systems when different bounds are considered for the use of the space resource. We consider in this paper two natural bounds: the amount of available physical space (in terms of the number of objects and membranes) and the organization of the membrane structure (in particular, concerning the depth of the membrane structure). We present the main results obtained so far on this subject.
7 December 2022 in Swarm and Evolutionary Computation