Abstract.
In this paper, we propose a method for communication between any two non-adjacent membranes in a membrane system. In order to get this we propose a new variant of P systems, P systems with message carriers, in which, whenever a source membrane wants to send some message to a destination membrane, it will create a message carrier with that message and send it to the destination. Here we define various communication modes for inter-membrane communication. This new variant of a P system is able to solve Traveling Salesperson Problem for weighted complete graphs in a time linear in the number of nodes in the graph and can simulate CD grammar systems with an external control. By ?external control? we mean controlling the sequence of components in action by a graph. We also prove that our new variant is computationally complete.