Membrane Computing: The Power of (Rule) Creation
Дата
Авторы
Arroyo,Fernando
Baranda,Angel
Castellanos,Juan
Paun,Gheorghe
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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