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.

Rewriting P Systems with Conditional Communication / Bottoni, Paolo Gaspare; Labella, Anna; Carlos Martin, Vide; Gheorghe, Paun. - STAMPA. - 2300(2002), pp. 325-353. [10.1007/3-540-45711-9_18].

Rewriting P Systems with Conditional Communication

BOTTONI, Paolo Gaspare;LABELLA, Anna;
2002

Abstract

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.
2002
Formal and Natural Computing. Essays Dedicated to Grzegorz Rozenberg
9783540431909
membrane system; natural computation
02 Pubblicazione su volume::02a Capitolo o Articolo
Rewriting P Systems with Conditional Communication / Bottoni, Paolo Gaspare; Labella, Anna; Carlos Martin, Vide; Gheorghe, Paun. - STAMPA. - 2300(2002), pp. 325-353. [10.1007/3-540-45711-9_18].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/247986
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact