Rewriting P Systems with Conditional Communication

TitleRewriting P Systems with Conditional Communication
Publication TypeJournal Papers
Year of Publication2002
AuthorsBottoni, P., Labella A., Martín-Vide C., & Paun G.
Journal TitleLecture Notes in Computer Science
Place PublishedAmsterdam, The Netherlands

A membrane system (P system) is a model of computation inspired by some basic features of the structure and behaviour of living cells. In this paper we consider systems with string-objects processed by rewriting, with the communication controlled by conditions on the contents of the strings. Symbols, substrings (in an arbitrary place, or as a prefix/suffix), or the shape of the whole string are used as permitting and as forbidding conditions when moving strings from a membrane to a neighboring membrane. Many of the obtained variants lead to new characterizations of recursively enumerable languages (as expected, these characterizations indicate a trade-off between the number of membranes and the strength of the communication conditions used). Several open problems are also formulated.

ISSN Number0302-9743