On descriptive complexity in P systems

Thu, 11/29/2007 - 14:20 — ana

Title	On descriptive complexity in P systems
Publication Type	Journal Papers
Year of Publication	2005
Authors	Gutiérrez-Naranjo, M. A., Pérez-Jiménez M. J., & Riscos-Núñez A.
Journal Title	Lecture Notes in Computer Science
ISBN Number	978-3-540-25080-7
Publisher	Springer
Place Published	Amsterdam, The Netherlands
Volume	3365
Pages	320-330
Abstract	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.
URL	http://www.springerlink.com/content/gvux7wbg16y3m6jg/?p=aec382c195614ca0a11739e4c1e790d8&pi=19
ISSN Number	0302-9743