Multidimensional descriptional complexity of P systems

Abstract

Membrane Computing is a branch of Natural Computing which starts from the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. The description of the complexity of the computations of the membrane devices (P systems) is a hard task which goes beyond the usual parameters of time and space. This is especially hard in the case of P systems where the number of membranes increases along the computation, via division or creation of membranes. In this paper we show that a four-dimensional carpet can be a useful tool to describe and compare evolutions of P systems, even in such cases.