%0 Generic
%D 2020
%T Cell-like P systems with polarizations and minimal rules
%A Linqiang Pan
%A David Orellana-Martín
%A Bosheng Song
%A Mario J. Pérez-Jiménez
%C Amsterdam (The Netherlands)
%I Elsevier
%K bio-inspired computing
%K Membrane computing
%K Minimal rule
%K Universality
%P 1-18
%R https://doi.org/10.1016/j.tcs.2019.10.001
%U http://www.sciencedirect.com/science/article/pii/S0304397519306231
%V 816
%X 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.
%8 05/2020