Bridging Membrane and Reaction Systems

TitleBridging Membrane and Reaction Systems
Publication TypeConference Contributions
Year of Publication2013
AuthorsPaun, G., Pérez-Jiménez M. J., & Rozenberg G.
Conference NameEleventh Brainstorming Week on Membrane Computing (11BWMC)
Volume TitleProceedings of the Eleventh Brainstorming Week on Membrane Computing (11BWMC)
ISBN Number978-84-940691-9-2
PublisherFénix Editora
Place PublishedSevilla, España
Date Published08/2013

This paper continues an investigation into bridging two research areas con-
cerned with natural computing: membrane computing and reaction systems. More specif-
ically, 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) SN P systems with non-permanency of spikes assumption charac-
terize 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.