Affiliations: Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucharest, Romania. george.paun@imar.ro, gpaun@us.es | Research Group on Natural Computing, Department of Computer Science and AI, University of Sevilla, Avda Reina Mercedes s/n, 41012 Sevilla, Spain. marper@us.es | Leiden Institute for Advanced Computer Science - LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands. rozenber@liacs.nl
Note: [] Also works: Research Group on Natural Computing, Department of Computer Science and AI, University of Sevilla, Avda Reina Mercedes s/n, 41012 Sevilla, Spain Address for correspondence: Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucharest, Romania
Abstract: This paper continues an investigation into bridging two research areas concerned with natural computing: membrane computing and reaction systems. More specifically, the paper considers a transfer of two assumptions/axioms of reaction systems, non-permanency and the threshold assumption, into the framework of membrane computing. It is proved that: (1) spiking neural P systems with non-permanency of spikes assumption characterize the semilinear sets of numbers, and (2) symport/antiport P systems with threshold assumption (translated as ω multiplicity of objects) can solve SAT in polynomial time. Also, several open research problems are stated.
Keywords: Membrane computing, reaction system, semilinear set, fypercomputation, SAT
