Membrane Computing: The Power of (Rule) Creation

TitleMembrane Computing: The Power of (Rule) Creation
Publication TypeJournal Papers
Year of Publication2002
AuthorsArroyo, F., Baranda A., Castellanos J., & Paun G.
Journal TitleJournal of Universal Computer Science
Place PublishedGranz Austria

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

Keywordschomsky hierarchy, Membrane computing, molecular computing, rewriting, splicing
ISSN Number0948-6968