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
Open Access
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.
molecular computing, membrane computing, Chomsky hierarchy, rewriting, splicing