P Systems with Symport/Antiport of Rules

Abstract

Moving \instructions" instead of \data", using transport mecha- nisms inspired by biology { this could represent, shortly, the basic idea of the computing device presented in this paper. Speci¯cally, we propose a new class of P systems that use, at the same time, evolution rules and symport/antiport rules. The idea of this kind of systems is simple: during a computation symbol- objects (the \data") evolve using evolution rules but they cannot be moved; on the other hand, the evolution rules (the \instructions") can be moved across the membranes using classical symport/antiport rules. We present di®erent results using di®erent combinations between the power of the evolution rules (catalytic, non-cooperative rules) and the weight of the symport/antiport rules. In particular, we show that, using non-cooperative rules and antiports of un- bounded weight is possible to obtain at least the Parikh set of ET0L languages. On the other hand, using catalytic rules (one catalyst) and antiports of weight 2, the system becomes universal. Several open problems are also presented.