Rewriting P systems: improved hierarchies

Generally, for proving universality results about rewriting P systems one considers matrix grammars in the strong binary normal form. Such grammars contain both matrices with rules used in the appearance checking mode and matrices without appearance checking rules. In the proofs of most of the universality theorems reported in the literature, appearance checking matrices are simulated by using only two membranes, while four membranes are used for simulating matrices without appearance checking rules. Thus, a way to improve these theorems is to diminish the number of membranes used for simulating matrices without appearance checking rules. In this paper we address this problem, and give first a general improved result about simulating matrix grammars without appearance checking: three membranes are shown to suffice. This result is then used to improve several universality results from various membrane computing papers, for instance, about P systems with replicated rewriting, with leftmost rewriting, with conditional communication, as well as for hybrid P systems with finite choice. © 2004 Elsevier B.V. All rights reserved.