A toolbox for simpler active membrane algorithms

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...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2017-04, Vol.673, p.42-57
Main Authors: Leporati, Alberto, Manzoni, Luca, Mauri, Giancarlo, Porreca, Antonio E., Zandron, Claudio
Format: Article
Language:English
Subjects:
Computational complexity
Membrane computing
P system with active membranes
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2017.03.015