The Power of Symport-3 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 neighboring region. It is known that P systems with symport rules of weight at most 3 and a single membrane are computationally complete with 7 superfluous symbols. It is also known that without any superfluous symbols such systems only generate finite sets. We improve the lower bounds on the generative power of P systems with few superfluous objects as follows. 0: empty set and all singletons; k: all sets with at most k elements and all sets of numbers k+regular with up to k states, 1 k 5; 6: all regular sets of non-negative integers. All results except the last one are also valid for different modes, e.g., sequential one, also for higher values of k.