We show that recogniser P systems with active membranes can be augmented with a priority over their set of rules and any number of membrane charges without loss of generality, as they can be simulated by standard P systems with active membranes, in particular using only two charges. Furthermore, we show that more general accepting conditions, such as sending out several, possibly contradictory results and keeping only the first one, or rejecting by halting without output, are also equivalent to the standard accepting conditions. The simulations we propose are always without significant loss of efficiency, and thus the results of this paper can hopefully simplify the design of algorithms for P systems with active membranes.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2017). A toolbox for simpler active membrane algorithms. THEORETICAL COMPUTER SCIENCE, 673, 42-57 [10.1016/j.tcs.2017.03.015].

A toolbox for simpler active membrane algorithms

LEPORATI, ALBERTO OTTAVIO
Primo
;
MANZONI, LUCA
Secondo
;
MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO
;
ZANDRON, CLAUDIO
Ultimo
2017

Abstract

We show that recogniser P systems with active membranes can be augmented with a priority over their set of rules and any number of membrane charges without loss of generality, as they can be simulated by standard P systems with active membranes, in particular using only two charges. Furthermore, we show that more general accepting conditions, such as sending out several, possibly contradictory results and keeping only the first one, or rejecting by halting without output, are also equivalent to the standard accepting conditions. The simulations we propose are always without significant loss of efficiency, and thus the results of this paper can hopefully simplify the design of algorithms for P systems with active membranes.
Articolo in rivista - Articolo scientifico
Computational complexity; Membrane computing; P system with active membranes;
Computational complexity; Membrane computing; P system with active membranes; Theoretical Computer Science; Computer Science (all)
English
22-mar-2017
2017
673
42
57
reserved
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2017). A toolbox for simpler active membrane algorithms. THEORETICAL COMPUTER SCIENCE, 673, 42-57 [10.1016/j.tcs.2017.03.015].
File in questo prodotto:
File Dimensione Formato  
2017_TCS_AToolbox.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 530.61 kB
Formato Adobe PDF
530.61 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/10281/152776
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 3
Social impact