JUCS - Journal of Universal Computer Science 8(3): 369-381, doi: 10.3217/jucs-008-03-0369
Membrane Computing: The Power of (Rule) Creation
expand article infoFernando Arroyo‡, Angel Baranda§, Juan Castellanos§, Gheorghe Paun|
‡ Dpto. de Lenguajes, Proyectos y Sistemas Informaticos, Escuela de Informática, Madrid, Spain§ Dpto. de Inteligencia Artificial Facultad de Informática, Madrid, Spain| Institute of Mathematics of the Romanian Academy, Bucharest, Romania

Corresponding author: Fernando Arroyo ( farroyo@eui.upm.es )

© Fernando Arroyo, Angel Baranda, Juan Castellanos, Gheorghe Paun.
This article is freely available under the J.UCS Open Content License.
Citation: Arroyo F, Baranda A, Castellanos J, Paun G (2002) Membrane Computing: The Power of (Rule) Creation. JUCS - Journal of Universal Computer Science 8(3): 369-381. https://doi.org/10.3217/jucs-008-03-0369
Open Access
Abstract
We consider a uniform way of treating objects and rules in P systems: we start with multisets of rules, which are consumed when they are applied, but the application of a rule may also produce rules, to be applied at subsequent steps. We find that this natural and simple feature is surprisingly powerful: systems with only one membrane can characterize the recursively enumerable languages, both in the case of rewriting and of splicing rules, the same result is obtained in the case of symbol-objects, for the recursively enumerable sets of vectors of natural numbers.
Keywords
molecular computing, membrane computing, Chomsky hierarchy, rewriting, splicing