Computational Complexity of Simple P Systems

• Autorzy: Ciobanu G. , Resios A.
• Języki publikacji: EN

Abstrakty

EN

This paper introduces a new class of membrane systems called simple P systems, and studies their computational complexity. We start by presenting the knapsack problem and its time complexity. Then we study the computational complexity of simple P systems by considering the allocation of resources enabling the parallel application of the rules. We show that the decision version of the resource allocation problem for simple P systems is NP-complete, by using the knapsack problem.

Słowa kluczowe

EN

membrane systems; knapsack problem; computational complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 1
• Strony: 49--59
• Opis fizyczny: bibliogr. 10 poz., tab.

Twórcy

autor

Ciobanu G.

autor

Resios A.

• Romanian Academy, Institute of Computer Science “A.I.Cuza” University of Ias¸i, Blvd. Carol I no.11, 700506 Iasi, Romania,

Bibliografia

• [1] G. Ciobanu, M. Gontineac. Mealy Membrane Automata and P Systems Complexity. Cellular Computing; Complexity Aspects, Fenix Editora, Sevilla, 149-164, 2005.
• [2] G. Ciobanu, Gh. Pǎun, M.J. Pérez-Jiménez. Application of Membrane Computing, Springer, 2006.
• [3] T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms, MIT Press, 1990.
• [4] M.A. Gutiérrez-Naranjo, M. Pérez Jiménez, A. Riscos-Núñez. On Descriptive Complexity of P Systems, Workshop on Membrane Computing, 320-330, 2004.
• [5] H. Kellerer, U. Pferschy, D. Pisinger. Knapsack Problems, Springer, 2004.
• [6] A. Leporati, C. Zandron, C. Ferretti, G. Mauri. Solving Numerical NP-Complete Problems with Spiking Neural P Systems, Workshop on Membrane Computing, 336-352, 2007.
• [7] Gh. Păun. P Systems with Active Membranes: Attacking NP Complete Problems, J. Autom. Lang. Comb. vol.6, 75-90, 2001.
• [8] Gh. Păun. Membrane Computing. An Introduction, Springer, 2002.
• [9] M. Pérez Jiménez, A.R. Jiménez, F. Sancho-Caparrini. Complexity Classes in Models of Cellular Computing with Membranes, Natural Computing vol.2, 265-285, 2003.
• [10] The P systems Webpage: http://ppage.psystems.eu