On descriptive complexity in P systems

TitleOn descriptive complexity in P systems
Publication TypeJournal Papers
Year of Publication2005
AuthorsGutiérrez-Naranjo, M. A., Pérez-Jiménez M. J., & Riscos-Núñez A.
Journal TitleLecture Notes in Computer Science
ISBN Number978-3-540-25080-7
Place PublishedAmsterdam, The Netherlands

In this paper we address the problem of describing the complexity of the evolution of a P system. This issue is is specially hard in the case of P systems with active membranes, where 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 some new parameters which can be used to compare evolutions of P systems. To illustrate this, we also include two different cellular solutions to the Subset Sum problem and compare them via these new parameters.

ISSN Number0302-9743