Mon, 10/21/2019 - 18:07 — mmartinez

Title | Cell-like P systems with polarizations and minimal rules |

Publication Type | Journal Papers |

Year of Publication | 2020 |

Authors | Pan, L., Orellana-Martín D., Song B., & Pérez-Jiménez M. J. |

Journal Title | Theoretical Computer Science |

Publisher | Elsevier |

Place Published | Amsterdam (The Netherlands) |

Volume | 816 |

Pages | 1-18 |

Date Published | 05/2020 |

Abstract | P systems with active membranes are a class of computation models in the area of membrane computing, which are inspired from the mechanism by which chemicals interact and cross cell membranes. In this work, we consider a normal form of P systems with active membranes, called cell-like P systems with polarizations and minimal rules, where rules are minimal in the sense that an object evolves to exactly one object with the application of an evolution rule or a communication rule, or an object evolves to two objects that are assigned to the two new generated membranes by applying a division rule. The present work investigates the computational power of P systems with polarizations and minimal rules. Specifically, results about Turing universality and non-universality are obtained with the combination of the number of membranes, the number of polarizations, and the types of rules. We also show that polarizationless P systems with minimal rules are equivalent to Turing machines working in a polynomial space, that is, the class of problems that can be solved in polynomial time by polarizationless P systems with minimal rules is equal to the class PSPACE. |

Keywords | bio-inspired computing, Membrane computing, Minimal rule, Universality |

URL | http://www.sciencedirect.com/science/article/pii/S0304397519306231 |

ISSN Number | 0304-3975 |

DOI | https://doi.org/10.1016/j.tcs.2019.10.001 |