Abstract
Up to now, P systems dealing with numerical problems have been rarely considered in the literature. In this paper we present an effective solution to the Knapsack problem using a family of deterministic P systems with active membranes using 2-division. We show that the number of steps of any computation is of linear order, but polynomial time is required for pre-computing resources.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cordón-Franco, A., Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Sancho-Caparrini, F.: A Prolog simulator for deterministic P systems with active membranes. New Generation Computing (to appear)
Păun, G.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000)
Păun, G.: Membrane Computing. An Introduction. Springer, Berlin (2002)
Păun, G., Rozenberg, G.: A guide to membrane computing. Theoretical Computer Sciences 287, 73–100 (2002)
Pérez-Jiménez, M.J., Riscos-Núñez, A.: Solving the Subset-Sum problem by active membranes. New Generation Computing (to appear)
Pérez-Jiménez, M.J., Romero-Jiménez, A., Sancho-Caparrini, F.: Teoría de la Complejidad en modelos de computation celular con membranes, Editorial Kronos, Sevilla (2002)
Pérez-Jiménez, M.J., Romero-Jiménez, A., Sancho-Caparrini, F.: A polynomial complexity class in P systems using membrane division. In: Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, Budapest, Hungary
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pérez-Jiménez, M.J., Riscos-Núñez, A. (2004). A Linear-Time Solution to the Knapsack Problem Using P Systems with Active Membranes. In: Martín-Vide, C., Mauri, G., Păun, G., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2003. Lecture Notes in Computer Science, vol 2933. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24619-0_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-24619-0_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20895-2
Online ISBN: 978-3-540-24619-0
eBook Packages: Springer Book Archive