Uniform Solution to Common Algorithmic Problem by P Systems Working in the Minimally Parallel Mode

• Autorzy: Niu Y. , Venkat I. , Khader A. T. , Subramanian K. G.

Identyfikatory

DOI

10.3233/FI-2015-1158

• Języki publikacji: EN

Abstrakty

EN

It is known that the Common Algorithmic Problem (CAP) has the nice property that several other NP-complete problems can be reduced to it in linear time. The decision version of this problemis known to be efficiently solved by a family of recognizer P systems with activemembranes with three electrical charges working in the maximally parallel way. We here work with a variant of P systems with active membranes without polarizations and present a uniform solution to CAP in the minimally parallel mode.

Słowa kluczowe

EN

membrane computing; P systems; minimal parallelism; common algorithmic problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 3
• Strony: 285--296
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Niu Y.

• School of Electronic Engineering and Computer Science Peking University, Beijing 100871, China

autor

Venkat I.

• School of Computer Sciences, Universiti Sains Malaysia Penang 11800, Malaysia

autor

Khader A. T.

• School of Computer Sciences, Universiti Sains Malaysia Penang 11800, Malaysia

autor

Subramanian K. G.

• School of Computer Sciences, Universiti Sains Malaysia Penang 11800, Malaysia

Bibliografia

• [1] Alhazov, A., Martín-Vide, C., Pan, L. Solving a PSPACE-complete problem by P systems with restricted active membranes. Fundamenta Informaticae, 58, 2(2003), 67–77.
• [2] Alhazov, A., Pan, L., Păun, Gh. Trading polarizations for labels in P systems with active membranes. Acta Informaticae, 41(2004), 111–144.
• [3] Alhazov, A., Pérez-Jiménez,M. J. Uniform solution of QSAT using polarizationless active membranes. Lecture Notes in Computer Science, 4664(2007), 122–133.
• [4] Ciobanu, G., Pan, L., Păun Gh., Pérez-Jiménez, M. J. P systems with minimal parallelism. Theoretical Computer Science, 378, 1(2007), 117–130.
• [5] Ciobanu, G., Pérez-Jiménez, M. J., Păun, Gh. eds. Applications of Membrane Computing. Springer–Verlag, Berlin (2006).
• [6] Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Riscos-Núñez, A., Romero-Campero, F.J. On the power of dissolution in P dystems with active membranes. Lecture Notes in Computer Science, 3850(2006), 224–240.
• [7] Head, T., Yamamura,M., Gal, S. Aqueous computing: writing on molecules. In: Proceedings of the Congress on Evolutionary Computation 1999, IEEE Service Center, Piscataway, NJ, 1106–1010.
• [8] Martín Vide, C., Pazos, J., Păun, G., Rodríguez Pat´on, A. Tissue P systems. Theoretical Computer Science, 296(2003), 295–326.
• [9] Pan, L.,Martín-Vide, C. Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes. Journal of Parallel and Distributed Computing, 65, 12(2005), 1578–1584.
• [10] Pan, L., Păun, Gh. Spiking neural P systems with anti-spikes. International Journal of Computers, Communications & Control, 4(2009), 139–150.
• [11] Pan, L., Păun, Gh. Spiking neural P systems: an improved normal form. Theoretical Computer Science, 411(2010), 906–918.
• [12] Pan, L., Pérez-Jiménez,M. J. Computational complexity of tissue-like P systems. Journal of Complexity, 26, 3(2010), 296–315.
• [13] Pan, L., Wang, J., Hoogeboom H. J. Spiking neural P systems with astrocytes. Neural Computation, 24, 3(2012), 805–825.
• [14] Pan, L., Zeng, X., Zhang, X. Time-free spiking neural P systems. Neural Computation, 5(2011), 1320–1342.
• [15] Pan, L., Zeng, X., Zhang, X., Jiang, Y. Spiking neural P systems with weighted synapses. Neural Processing Letters, 35, 1(2012), 13–27.
• [16] Păun, Gh. Computing with membranes. Journal of Computer and System Sciences, 61, 1(2000), 108–143.
• [17] Păun, Gh. Membrane Computing: An Introduction. Springer–Verlag, Berlin (2002).
• [18] Păun, Gh., Rozenberg, G., Salomaa, A. Handbook of membrane computing. Oxford University Press (2009).
• [19] Pérez-Jiménez, M. J., Romero-Campero, F.J. Attacking the common algorithmic problem by recognizer P systems. Lecture Notes in Computer Science, 3354(2005), 304–315.
• [20] Sakellariou, I., Stamatopoulou, I., Kefalas, P. Using membranes to model a multi-agent system towards underground metro station crowd behaviour simulation. ECAI 2012 Workshop, Montpellier, France, August 28, 2012, 5–10.
• [21] Song, T., Pan, L., Păun, Gh. Asynchronous spiking neural P systems with local synchronization. Information Sciences, 219(2013), 197–207.
• [22] Song, T., Pan, L., Wang, J., Venkat, I., Subramanian, K.G., Abdullah, R. Normal Forms of Spiking Neural P Systems With Anti-Spikes, IEEE Transactions on Nanobioscience, 11(2012), 352–359.
• [23] Wang, J., Hoogeboom, H.J., Pan, L., Păun, Gh. Pérez-Jiménez, M.J. Spiking neural P systems with weights. Neural Computation, 22(2010), 2615–2646.
• [24] Zhang, X., Wang, S., Niu, Y., Pan, L. Tissue P systems with cell separation: attacking the partition problem. Science China Information Sciences, 54(2011), 293–304.