One-membrane symport with few extra symbols

Abstract

Membrane systems (with symbol objects) are formal models of distributed parallel multiset processing. Symport rules move multiple objects to a neighbouring region. It is known that for P systems with symport rules of weight at most 3 and a single membrane, seven superfluous symbols are enough for computational completeness, and one is necessary. We present the improvements of the lower bounds on the generative power of P systems with symport of weight bounded by 3 and 4, in particular, establishing that six and two extra symbols suffice, respectively. Besides maximally parallel P systems, we also consider sequential ones. In fact, all presented non-universality lower bound results, together with all upper bound results, hold also in this case, yielding the current state of the art.

Keywords:

• membrane computing
• distributed multiset processing
• symport
• theory of computing
• formal language theory

2010 AMS Subject Classifications :

• 03D25
• 68Q05
• 68Q10
• 68Q17
• 68Q45

ACM Computing System Classification Codes :

• F.1.1
• F.4.2
• F.4.3

Acknowledgements

The first author acknowledges the project RetroNet by the Lombardy Region of Italy under the ASTIL Program (regional decree 6119, 20100618).