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

Issue title: 9th edition of the international conference Bio-Inspired Computing: Theories and Applications, BIC-TA, 2014

Article type: Research Article

Authors: Niu, Yunyun | Venkat, Ibrahim | Khader, Ahamad Tajudin | Subramanian, K.G.

Affiliations: School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China. [email protected] | School of Computer Sciences, Universiti Sains Malaysia, Penang 11800, Malaysia. [email protected], [email protected], [email protected]

Note: [] Address for correspondence: Peking University, Beijing 100871, China

Abstract: 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 problem is known to be efficiently solved by a family of recognizer P systems with active membranes 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.

Keywords: Membrane Computing, P System, Minimal Parallelism, Common Algorithmic Problem

DOI: 10.3233/FI-2015-1158

Journal: Fundamenta Informaticae, vol. 136, no. 3, pp. 285-296, 2015