Evolution-Communication P Systems: Time-Freeness

Abstract

Membrane computing is a (biologically motivated) theoretical framework of distributed parallel computing. If symbol-objects are considered, then membrane sys- tems (also called P systems) are distributed multiset processing systems. In evolution- communication (EC) P systems the computation is carried out with the use of non- cooperative rewriting rules and with (usually the minimally cooperative) transport rules. The goal of this article is to improve the existing results on evolution-communication P systems. It is known that EC P systems with 2 membranes are universal, and so are time-free EC P systems with targets with 3 membranes. We prove that any recursively enumerable set of vectors of nonnegative integers can be generated by time-free EC P systems (without targets) with 2 membranes, thus improving both results.