Cell-like P systems with evolutional symport/antiport rules and membrane creation

Abstract

Cell-like P systems with symport/antiport rules are computing models inspired by theconservation law, in the sense that they compute by changing the places of objectswith respect to the membranes, and not by changing the objects themselves. In thiswork, a variant of these kinds of membrane systems, called cell-like P systems withevolutionalsymport/antiport rules, where objects can evolve in the execution of suchrules, is introduced. Besides, inspired by the autopoiesis process (ability of a system tomaintain itself), membrane creation rules are considered as an efficient mechanism toprovide an exponential workspace in terms of membranes. The presumed efficiency ofthese computing models (ability to solve computationally hard problems in polynomialtime and uniform way) is explored. Specifically, an efficient solution to theSATproblemis provided by means of a family of recognizer cell-like P systems with evolutionalsymport/antiport rules and membrane creation which make use of communication rulesinvolving a restricted number of objects.