P Systems with Limited Capacity

Abstract

P systems are a model of compartmentalized multiset rewriting inspired by the structure and functioning of the living cell. In this paper, we focus on a variant in P systems in which membranes have limited capacity, i.e., the number of objects they may hold is statically bounded. This feature corresponds to an important physical property of cellular compartments. We propose several possible semantics of limited capacity and show that one of them allows real-time simulations of partially blind register machines, while the other one allows for obtaining computational completeness.