On the Power of P Systems with Contextual Rules

Issue title: Membrane Computing (WMC-CdeA2001)

Article type: Research Article

Authors: Krishna, S.N. | Lakshmanan, K. | Rama, R.

Affiliations: Department of Mathematics, Indian Institute of Technology, Madras, Chennai-36, Tamilnadu, India

Abstract: We consider P Systems with string objects which evolve by means of one-sided contextual rules and erasing contextual rules. The generative power of these systems with three or less than three membranes is investigated. We show that systems with three membranes characterize the family of recursively enumerable languages. When the string replication is used in one-sided contextual rules, these systems are able of solving NP-complete problems in linear time: this is exemplified with SAT and HPP.

Keywords: P Systems, One-sided contextual rules, Erasing contextual rules, Recursively enumerable, NP-completeness

Journal: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 167-178, 2002