The environment as a frontier of efficiency in tissue P systems with communication rules

Originally, in P systems the environment plays a passive role; that is, it can only receive objects, without having the ability to send objects to the system. Later, tissue P systems were introduced, where the cells are located in the environment in the sense that they can communicate between each other but also with the environment. In fact, a special alphabet was introduced as a way to symbolize the chemical elements available in it and that can interact with the cells. In the framework of membrane computing, all the objects of this alphabet are present in the environment with an arbitrary multiplicity at the beginning of the computation; that is, there are enough objects of this type in the environment to fire the rules that can be fired by these objects. From the computational complexity point of view, it seems to be a very strong ingredient, since it adds a virtually infinite number of objects to the system in the whole computation. In this paper, we demonstrate that the behaviour of this special alphabet can be simulated by a generation stage ruled by evolutional communication rules and/or division/separation rules, such that the ability of these systems to efficiently solve presumably hard problems is not changed if the environment does not play an active role. (c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

Automated summary

P systems are computational models where the environment plays a passive role and later tissue P systems were introduced allowing communication between cells and the environment. A special alphabet represents the chemical elements and their interaction with cells. The behavior of this alphabet can be simulated by evolutionary communication rules and/or division/separation rules, maintaining efficiency even if the environment is not active.