A Survey of Nature-Inspired Computing: Membrane Computing

TitleA Survey of Nature-Inspired Computing: Membrane Computing
Publication TypeJournal Papers
Year of Publication2021
AuthorsSong, B., Li K., Orellana-Martín D., Pérez-Jiménez M. J., & Pérez-Hurtado I.
Journal TitleACM Computing Surveys
PublisherAssociation for Computing Machinery
Place PublishedNew York, NY, USA
Volume54
PagesArticle no 22
Abstract

Nature-inspired computing is a type of human-designed computing motivated by nature, which is based on the employ of paradigms, mechanisms, and principles underlying natural systems. In this article, a versatile and vigorous bio-inspired branch of natural computing, named membrane computing is discussed. This computing paradigm is aroused by the internal membrane function and the structure of biological cells. We first introduce some basic concepts and formalisms of membrane computing, and then some basic types or variants of P systems (also named membrane systems) are presented. The state-of-the-art computability theory and a pioneering computational complexity theory are presented with P system frameworks and numerous solutions to hard computational problems (especially NP-complete problems) via P systems with membrane division are reported. Finally, a number of applications and open problems of P systems are briefly described.

KeywordsComputational Complexity, distributed systems, Membrane computing, Nature-inspired computing
URLhttps://doi.org/10.1145/3431234
ISSN Number0360-0300
DOI10.1145/3431234