Chapter of Book
On Descriptive Complexity of P Systems
Author/s | Gutiérrez Naranjo, Miguel Ángel
Pérez Jiménez, Mario de Jesús Riscos Núñez, Agustín |
Department | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Publication Date | 2005 |
Deposit Date | 2017-01-13 |
Published in |
|
ISBN/ISSN | 978-3-540-25080-7 0302-9743 |
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 ... 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. |
Funding agencies | Ministerio de Ciencia y Tecnología (MCYT). España |
Project ID. | TIC2002-04220-C03-01 |
Citation | Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J., y Riscos Núñez, A. (2005). On Descriptive Complexity of P Systems. En Membrane Computing, 5th International Workshop, WMC5, Revised Selected and Invited Papers. Lecture Notes in Computer Science, 3365 (2005) (pp. 320-330). Berlin: Springer. |
Files | Size | Format | View | Description |
---|---|---|---|---|
chp%3A10.1007%2F978-3-540-3183 ... | 458.8Kb | [PDF] | View/ | |