Multidimensional Sevilla carpets Associated with P Systems

Abstract

In this paper we address the problem of describing the complexity of the evolution of a P system. This is especially difficult in the case of P systems where the number of membranes in creases along the computation, via division or creation of membranes. In these cases the number of steps of a computation is not sufficient to evaluate the complexity. Sevilla Carpets were introduced in [1℄, and they describe the space-time complexity of P systems. Based on them, we de ne a four-dimensional manifold whih can be used to compare evolutions of P systems.