Contextual P Systems

Issue title: Membrane Computing (WMC-CdeA2001)

Article type: Research Article

Authors: Krithivasan, Kamala | Madhu, Mutyam

Affiliations: Theoretical Computer Science Laboratory, Dept. of Computer Science and Engineering, Indian Institute of Technology, Madras, Chennai-36, Tamil Nadu, India

Abstract: Generally, in P systems with string-objects one uses the Chomsky way of rewriting for processing the objects. In this paper we consider the contextual way of handling string-objects in P systems. We introduce some variants of contextual grammars and prove that contextual P systems with rules corresponding to these variants are more powerful than ordinary contextual grammars and their variants. We also show that one-sided contextual P systems with right-sided erased contexts and insertion contextual P systems with right-sided erased contexts are computationally complete.

Keywords: P systems, contextual grammars, insertion grammars, contextual P systems, recursively enumerable languages, Kuroda normal form, Pentonnen normal form, computational completeness

Journal: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 179-189, 2002