Repositorio de producción científica de la Universidad de Sevilla

On Descriptive Complexity of P Systems

 

Advanced Search
 
Opened Access On Descriptive Complexity of P Systems
Cites

Show item statistics
Icon
Export to
Author: 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
Date: 2005
Published in: Membrane Computing, 5th International Workshop, WMC5, Revised Selected and Invited Papers. Lecture Notes in Computer Science, 3365 (2005)
ISBN/ISSN: 978-3-540-25080-7
0302-9743
Document type: Chapter of Book
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.
Size: 458.8Kb
Format: PDF

URI: http://hdl.handle.net/11441/52254

DOI: 10.1007/978-3-540-31837-8_20

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)