Multidimensional Sevilla Carpets associated with P systems

TitleMultidimensional Sevilla Carpets associated with P systems
Publication TypeContributions to Book Chapters
Year of Publication2005
AuthorsGutiérrez-Naranjo, M. A., Pérez-Jiménez M. J., & Riscos-Núñez A.
EditorsGutiérrez-Naranjo, M. A., Paun G., & Pérez-Jiménez M. J.
Book TitleCellular Computing (Complexity Aspects)
ISBN Number84-609-5338-6
PublisherFénix Editora
Place PublishedSevilla, Spain

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 increases 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 define a four-dimensional manifold which can be used to compare evolutions of P systems.

esf-2.pdf104.05 KB